License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-94930
URL:

; ;

On the Tractability of Optimization Problems on H-Graphs

 pdf-format:

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 Seminar: 26th Annual European Symposium on Algorithms (ESA 2018) Issue date: 2018 Date of publication: 2018

DROPS-Home | Fulltext Search | Imprint | Privacy