Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs

DOI10.1007/s00453-018-0479-5zbMath1428.05291arXiv1804.04077OpenAlexW2963740725MaRDI QIDQ1725633

Marcin Pilipczuk, Gábor Bacsó, Zsolt Tuza, Daniel Lokshtanov, Erik Jan van Leeuwen, Dániel Marx

Publication date: 14 February 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.04077

zbMATH Keywords

approximationindependent set\(H\)-free graphssubexponential algorithmsscattered set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Unnamed Item ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Unnamed Item ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ \(H\)-colouring \(P_t\)-free graphs in subexponential time ⋮ Parameterized complexity of independent set in H-free graphs ⋮ On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• On maximum independent sets in \(P_{5}\)-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Powers of geometric intersection graphs and dispersion algorithms
• Which problems have strongly exponential complexity?
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Facility dispersion problems under capacity and cost constraints
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Parametrized complexity theory.
• Fast Sub-exponential Algorithms and Compactness in Planar Graphs
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Independence and Efficient Domination on P₆-free Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Parameterized Algorithms
• On locally optimal independent sets and vertex covers
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)

This page was built for publication: Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs