Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs

DOI10.1137/1.9781611975482.77zbMath1431.68047arXiv1707.05491OpenAlexW2737177295MaRDI QIDQ5236261

Marcin Pilipczuk, Tereza Klimošová, Michał Pilipczuk, Andrzej Grzesik

Publication date: 15 October 2019

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

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

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 (30)

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ Computing weighted subset transversals in \(H\)-free graphs ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ 1-extendability of independent sets ⋮ Graphs with polynomially many minimal separators ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Unnamed Item ⋮ 1-extendability of independent sets ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Colouring (P_r+P_s)-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 ⋮ Vertex cover at distance on \(H\)-free graphs

This page was built for publication: Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs