Maximum weight independent set for claw-free graphs in polynomial time

DOI10.1016/J.DAM.2017.11.029zbMATH Open1380.05147arXiv1602.05838OpenAlexW2964197964MaRDI QIDQ1701093FDOQ1701093

Authors: Andreas Brandstädt, Raffaele Mosca 

Publication date: 22 February 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The Maximum Weight Independent Set (MWIS) problem is a well-known NP-hard problem. For graphs $G_1,G_2$, $G_1+G_2$ denotes the disjoint union of $G_1$ and $G_2$, and for a constant $lge2$, $lG$ denotes the disjoint union of $l$ copies of $G$. A {em claw} has vertices $a,b,c,d$, and edges $ab,ac,ad$. MWIS can be solved for claw-free graphs in polynomial time; the first two polynomial time algorithms were introduced in 1980 by cite{Minty1980,Sbihi1980}, then revisited by cite{NakTam2001}, and recently improved by cite{FaeOriSta2011,FaeOriSta2014}, and by cite{NobSas2011,NobSas2015} with the best known time bound in cite{NobSas2015}. Furthermore MWIS can be solved for the following extensions of claw-free graphs in polynomial time: fork-free graphs cite{LozMil2008}, $K_2$+claw-free graphs cite{LozMos2005}, and apple-free graphs cite{BraLozMos2010,BraKleLozMos2008}. This manuscript shows that for any constant $l$, MWIS can be solved for $l$claw-free graphs in polynomial time. Our approach is based on Farber's approach showing that every $2K_2$-free graph has $calO(n^2)$ maximal independent sets cite{Farbe1989}, which directly leads to a polynomial time algorithm for MWIS on $2K_2$-free graphs by dynamic programming. Solving MWIS for $l$claw-free graphs in polynomial time extends known results for claw-free graphs, for $l{K}_2$-free graphs for any constant $l$ cite{Aleks1991,FarHujTuz1993,Prisn1995,TsuIdeAriShi1977}, for $K_2$+claw-free graphs, for $2P_3$-free graphs cite{LozMos2012}, and solves the open questions for $2K_2+P_3$-free graphs and for $P_3$+claw-free graphs being two of the minimal graph classes, defined by forbidding one induced subgraph, for which the complexity of MWIS was an open problem.

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

Recommendations

• Maximum weight independent sets in classes related to claw-free graphs
• Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.

zbMATH Keywords

polynomial timemaximum weight independent set problem\(\ell\)claw-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• Reducibility among combinatorial problems
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Independent set in \(P_5\)-free graphs in polynomial time
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Title not available (Why is that?)
• On diameters and radii of bridged graphs
• Independent sets of maximum weight in apple-free graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• On graphs with polynomially solvable maximum-weight clique problem
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Title not available (Why is that?)
• Solving the weighted stable set problem in claw-free graphs via decomposition
• Independent Sets of Maximum Weight in Apple-Free Graphs
• Title not available (Why is that?)
• From matchings to independent sets
• A reduction algorithm for the weighted stable set problem in claw-free graphs

Cited In (19)

• Title not available (Why is that?)
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Simple games versus weighted voting games: bounding the critical threshold value
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Feedback vertex set and even cycle transversal for \(H\)-free graphs: finding large block graphs
• Treewidth versus clique number. II: Tree-independence number
• Vertex cover at distance on \(H\)-free graphs
• Title not available (Why is that?)
• An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
• Maximum weight independent sets in classes related to claw-free graphs
• New results on independent sets in extensions of \(2K_2\)-free graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• 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
• Title not available (Why is that?)
• Reconfiguring independent sets in claw-free graphs
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs

This page was built for publication: Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1701093)