Independent Set in P5-Free Graphs in Polynomial Time

DOI10.1137/1.9781611973402.43zbMath1422.68126OpenAlexW2486237862MaRDI QIDQ5384003

Yngve Villanger, Martin Vatshelle, Daniel Lokshantov

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.43

Mathematics Subject Classification ID

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

Related Items

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ A new characterization of \(P_k\)-free graphs ⋮ Solving Problems on Graphs of High Rank-Width ⋮ Vizing bound for the chromatic number on some graph classes ⋮ Triangle-free graphs with no six-vertex induced path ⋮ Tent and a subclass of \(P_{5}\)-free graphs ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Boundary classes for graph problems involving non-local properties ⋮ Polynomial size IP formulations of knapsack may require exponentially large coefficients ⋮ Excluding hooks and their complements ⋮ Graphs with polynomially many minimal separators ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ More results on weighted independent domination ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ A polytime preprocess algorithm for the maximum independent set problem ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Unnamed Item ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Solving problems on graphs of high rank-width ⋮ Unnamed Item ⋮ A note on efficient domination in a superclass of \(P_5\)-free graphs ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ Coloring graphs characterized by a forbidden subgraph ⋮ Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Parameterized Complexity of Independent Set in H-Free Graphs. ⋮ Critical hereditary graph classes: a survey ⋮ Approximating weighted induced matchings ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ On the maximum independent set problem in subclasses of subcubic graphs ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ Maximum colorful independent sets in vertex-colored graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ 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 ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ Independent Feedback Vertex Set for P_5-free Graphs ⋮ Vertex cover at distance on \(H\)-free graphs ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs