Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances

Tim A. Hartmann, Dániel Marx

The distance-d variants of Independent Set and Dominating Set problems have been extensively studied from different algorithmic viewpoints. In particular, the complexity of these p…