H-free graphs, Independent Sets, and subexponential-time algorithms
  • Metaadatok
Tartalom: http://real.mtak.hu/74267/
Archívum: MTA Könyvtár
Gyűjtemény: Status = Published

Type = Book Section
Cím:
H-free graphs, Independent Sets, and subexponential-time algorithms
Létrehozó:
Bacsó, Gábor
Marx, Dániel
Tuza, Zsolt
Közreműködő:
Guo, J.
Hermelin, D.
Kiadó:
Schloss Dagstuhl Leibniz-Zentrum fĂĽr Informatik
Dátum:
2017
Téma:
QA166-QA166.245 Graphs theory / gráfelmélet
QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Tartalmi leírás:
It is an old open question in algorithmic graph theory to determine the complexity of the Maximum Independent Set problem on Pt-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t ≤ 5 [Lokshtanov et al., SODA 2014, pp. 570-581, 2014]. Here we study the existence of subexponential-time algorithms for the problem: by generalizing an earlier result of Randerath and Schiermeyer for t = 5 [Discrete Appl. Math., 158 (2010), pp. 1041-1044], we show that for any t ≥ 5, there is an algorithm for Maximum Independent Set on Pt-free 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 d-Scattered Set on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus number of edges): If every component of H is a path, then d-Scattered Set on H-free graphs with n vertices and m edges can be solved in time 2(n+m) 1-O(1/|V (H)|), even if d is part of the input. Otherwise, assuming ETH, there is no 2o(n+m)-time algorithm for d-Scattered Set for any fixed d ≥ 3 on H-free graphs with n-vertices and m-edges. © 2016 Gábor Bacsó, Dániel Marx, and Zsolt Tuza.
Nyelv:
angol
Típus:
Book Section
PeerReviewed
info:eu-repo/semantics/bookPart
Formátum:
text
Azonosító:
Bacsó, Gábor and Marx, Dániel and Tuza, Zsolt (2017) H-free graphs, Independent Sets, and subexponential-time algorithms. In: 11th International Symposium on Parameterized and Exact Computation, IPEC 2016. Leibniz International Proceedings in Informatics, LIPIcs (63). Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, 3:1-3:12. ISBN 9783959770231
Kapcsolat:
MTMT:3284190; doi:10.4230/LIPIcs.IPEC.2016.3