2018/04/11 by Gábor Bacsó, Bacsó, Gábor, Daniel Lokshtanov +9
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1804.04077
openalex publication_date 2018/04/11 · openalex created_date 2018/04/24 · openalex updated_date 2026/07/28
In algorithmic graph theory, a classic open question is 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, 570--581, 2014], and an algorithm for t=6 announced recently [Grzesik et al. Arxiv 1707.05491, 2017]. Here we study the existence of subexponential-time algorithms for the problem: we show that for any t≥ 1, there is an algorithm for Maximum Independent Set on Pt-free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in 2^O(√ tn log n) time on Pt-free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. 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 the 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 2O(|V(H)|√(n+m)log (n+m)), even if d is part of the input. Otherwise, assuming the Exponential-Time Hypothesis (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.