Independent Set in P₅-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 (62)

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

This page was built for publication: Independent Set in P₅-Free Graphs in Polynomial Time

Independent Set in P5-Free Graphs in Polynomial Time

Independent Set in P₅-Free Graphs in Polynomial Time