Fomin, Fedor V. ;
Golovach, Petr A. ;
Raymond, JeanFlorent
On the Tractability of Optimization Problems on HGraphs
Abstract
For a graph H, a graph G is an Hgraph 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 circulararc graph. This notion was introduced in the early 1990s by Biro, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of Hgraphs by showing that a number of fundamental optimization problems like Clique, Independent Set, or Dominating Set are solvable in polynomial time on Hgraphs. We extend and complement these algorithmic findings in several directions.
First we show that for every fixed H, the class of Hgraphs is of logarithmicallybounded booleanwidth. We also prove that Hgraphs are graphs with polynomially many minimal separators. Pipelined with the plethora of known algorithms on graphs of bounded booleanwidth and graphs with polynomially many minimal separators, this describes a large class of optimization problems that are solvable in polynomial time on Hgraphs.
The most fundamental optimization problems among those solvable in polynomial time on Hgraphs 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 fixedparameter 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 JeanFlorent Raymond},
title = {{On the Tractability of Optimization Problems on HGraphs}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {30:130:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9493},
URN = {urn:nbn:de:0030drops94930},
doi = {10.4230/LIPIcs.ESA.2018.30},
annote = {Keywords: Htopological intersection graphs, parameterized complexity, minimal separators, booleanwidth, mimwidth}
}
2018
Keywords: 

Htopological intersection graphs, parameterized complexity, minimal separators, booleanwidth, mimwidth 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 