Bacsó, Gábor ;
Marx, Dániel ;
Tuza, Zsolt
HFree Graphs, Independent Sets, and SubexponentialTime Algorithms
Abstract
It is an outstanding open question in algorithmic graph theory to determine the complexity of the MAXIMUM INDEPENDENT SET problem on P_tfree graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomialtime algorithms are known only for t at most 5 [Lokshtanov et al., SODA 2014, 570581, 2014]. Here we study the existence of subexponentialtime algorithms for the problem: by generalizing an earlier result of Randerath and Schiermeyer for t=5 [Discrete App. Math., 158 (2010), 10411044], we show that for any t at least 5, there is an algorithm for MAXIMUM INDEPENDENT SET on P_tfree graphs whose running time is subexponential in the number of vertices.
SCATTERED SET is the generalization of MAXIMUM INDEPENDENT SET where the vertices of the solution are required to be at distance at least $d$ from each other. We give a complete characterization of those graphs H for which SCATTERED SET on Hfree graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges):
* If every component of H is a path, then dSCATTERED SET on Hfree graphs with n vertices and m edges can be solved in time 2^{(n+m)^{1O(1/V(H))}}, even if d is part of the input.
* Otherwise, assuming ETH, there is no 2^{o(n+m)} time algorithm for dSCATTERED SET for any fixed d at least 3 on Hfree graphs with n vertices and m edges.
BibTeX  Entry
@InProceedings{bacs_et_al:LIPIcs:2017:6939,
author = {G{\'a}bor Bacs{\'o} and D{\'a}niel Marx and Zsolt Tuza},
title = {{HFree Graphs, Independent Sets, and SubexponentialTime Algorithms}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {3:13:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770231},
ISSN = {18688969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6939},
URN = {urn:nbn:de:0030drops69397},
doi = {10.4230/LIPIcs.IPEC.2016.3},
annote = {Keywords: independent set, scattered set, subexponential algorithms, Hfree graphs}
}
09.02.2017
Keywords: 

independent set, scattered set, subexponential algorithms, Hfree graphs 
Seminar: 

11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Issue date: 

2017 
Date of publication: 

09.02.2017 