Showing 2026Show all
2 papers · 1 filter
cs.DS2026
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…
math.CO2026
Steiner Forest for -Subgraph-Free Graphs
Tala Eagling-Vose, David C. Kutner, Felicia Lucke +4
Our main result is a full classification, for every connected graph , of the computational complexity of Steiner Forest on -subgraph-free graphs. To obtain this dichotomy, we…