License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.30
URN: urn:nbn:de:0030-drops-94930
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9493/
Fomin, Fedor V. ;
Golovach, Petr A. ;
Raymond, Jean-Florent
On the Tractability of Optimization Problems on H-Graphs
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. These graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This notion was introduced in the early 1990s by Biro, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of H-graphs by showing that a number of fundamental optimization problems like Clique, Independent Set, or 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. We also prove that H-graphs are graphs with polynomially many minimal separators. Pipelined with the plethora of known algorithms on graphs of bounded boolean-width and graphs with polynomially many minimal separators, this describes a large class of optimization problems that are solvable in polynomial time on H-graphs.
The most fundamental optimization problems among those solvable in polynomial time on H-graphs are Clique, Independent Set, and Dominating Set. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that Independent Set and 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, Dominating Set is fixed-parameter tractable (FPT) parameterized by the size of H. Besides, we show that Clique admits a polynomial kernel parameterized by H and the solution size.
BibTeX - Entry
@InProceedings{fomin_et_al:LIPIcs:2018:9493,
author = {Fedor V. Fomin and Petr A. Golovach and Jean-Florent Raymond},
title = {{On the Tractability of Optimization Problems on H-Graphs}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {30:1--30:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9493},
URN = {urn:nbn:de:0030-drops-94930},
doi = {10.4230/LIPIcs.ESA.2018.30},
annote = {Keywords: H-topological intersection graphs, parameterized complexity, minimal separators, boolean-width, mim-width}
}
|
Keywords: |
|
H-topological intersection graphs, parameterized complexity, minimal separators, boolean-width, mim-width |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
