On the Tractability of Optimization Problems on H -Graphs
- PDF / 6,586,289 Bytes
- 42 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 187 Views
On the Tractability of Optimization Problems on H‑Graphs Fedor V. Fomin1 · Petr A. Golovach1 · Jean‑Florent Raymond2 Received: 10 September 2018 / Accepted: 23 February 2020 © The Author(s) 2020
Abstract For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This class was introduced in the early 1990s by Bíró, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of H-graphs by showing that a number of fundamental optimization problems like Maximum Clique, Maximum Independent Set, or Minimum Dominating Set are solvable in polynomial time on H-graphs. We extend and complement these algorithmic findings in several directions. First we show that for every fixed H, the class of H-graphs is of logarithmically-bounded boolean-width (via mim-width). Pipelined with the plethora of known algorithms on graphs of bounded boolean-width, this describes a large class of problems solvable in polynomial time on H-graphs. We also observe that H-graphs are graphs with polynomially many minimal separators. Combined with the work of Fomin, Todinca and Villanger on algorithmic properties of such classes of graphs, this identify another wide class of problems solvable in polynomial time on H-graphs. The most fundamental optimization problems among the problems solvable in polynomial time on H-graphs are Maximum Clique, Maximum Independent Set, and Minimum Dominating Set. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that Maximum Independent Set and Minimum Dominating Set are W[1]-hard being parameterized by the size of H plus the size of the solution. On the other hand, we prove that when H is a tree, then Minimum Dominating Set is fixed-parameter tractable parameterized by the size of H. For Maximum Clique we show that it admits a polynomial kernel parameterized by H and the solution size. Keywords H-topological intersection graphs · Mim-width · Minimal separators · Dominating set
An extended abstract of this work appeared in the proceedings of ESA 2018 [14]. * Fedor V. Fomin [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
Mathematics Subject Classification 05C62 · 05C85 · 05C69 · 68R10
1 Introduction The notion of H-graph was introduced in the work of Bíró et al. [4] on precoloring extensions of graphs. H-graphs nicely generalize several popular and widely studied classes of graphs. For example, the classical definition of an interval graph is as a graph which is an intersection graph1 of intervals of a line. Equivalently, a graph is interval if it is an intersection graph of some subpaths of a path. Or, equivalently, if it is an intersection graph of some subgraphs of some subdivision (which is a graph obtained by placing vertices of degree 2 on the edges) of P2 , the graph with two
Data Loading...
