5 papers
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…
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…
Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
Florian Hörsch, Dániel Marx
Given a graph , a set of terminal vertices, and a demand graph on , the \textsc{Multicut} problem asks for a set of edges of minimum weight that separates the pairs o…
From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
Fabian Frei, Ahmed Ghazy, Tim A. Hartmann +2
A well-studied continuous model of graphs considers each edge as a continuous unit-length interval of points. In the problem -Tour defined within this model, the objective to f…
From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours -Covering All Points on All Edges
Fabian Frei, Ahmed Ghazy, Tim A. Hartmann +2
A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. For…