Representative Sets in Propositional Abduction

This paper studies a representation problem for propositional abduction. Given a set of explanations S, it asks whether every other explanation is represented by some member of S, meaning their symmetric difference is smaller than a threshold k. The authors provide a complete classification from the classical complexity perspective and analyze tractable and hard cases under several parameters. A notable result is that a full parameterized classification would require resolving the parameterized complexity of the covering radius problem from coding theory, exposing a previously unreported connection between coding theory and non-monotonic reasoning.