|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Maximum Weight Independent Set in lClaw-Free Graphs in Polynomial Time | | Andreas Brandstadt
; Raffaele Mosca
; | | Date: |
18 Feb 2016 | | 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 $l ge 2$, $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 ${cal O}(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 $lK_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. | | Source: | arXiv, 1602.5838 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER