research-article

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Authors:

Gianpaolo Oriolo,

Gautier StaufferAuthors Info & Claims

Journal of the ACM (JACM), Volume 61, Issue 4

Article No.: 20, Pages 1 - 41

https://doi.org/10.1145/2629600

Published: 01 July 2014 Publication History

Abstract

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(|V|(|E| + |V| log|V|))-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present article. Despite being weaker than the structural results for claw-free graphs given by Chudnovsky and Seymour [2005, 2008a, 2008b] our decomposition theorem is, on the other hand, algorithmic, that is, it is coupled with an O(|V||E|)-time algorithm that actually produces the decomposition.

References

[1]

R. Ahuja, T. L. Magnanti, and J. B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ.

Digital Library

[2]

F. Bonomo, G. Oriolo, and C. Snels. 2012. Minimum weighted clique cover on strip-composed perfect graphs. In Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science. Martin Charles Golumbic, Michal Stern, Avivit Levy, and Gila Morgenstern Eds., 22--33.

Digital Library

[3]

A. Brandstädt and F. F. Dragan. 2003. On linear and circular structure of (claw, net)-free graphs. Disc. Appl. Math. 129, 285--303.

Digital Library

[4]

A. Brandstädt and C. Hoáng. 2007. On clique separators, nearly chordal graphs, and the maximum weight stable set problem. Theoret. Comput. Sci. 389, 295--306.

Digital Library

[5]

M. Chudnovsky and P. Seymour. 2005. The structure of claw-free graphs. In Surveys in Combinatorics 2005, London Mathematics Society. Lecture Note Series 327, 153--171.

[6]

M. Chudnovsky and P. Seymour. 2008a. Claw-free graphs IV. Decomposition theorem. J. Combinat. Theory Ser B 98, 839--938.

Digital Library

[7]

M. Chudnovsky and P. Seymour. 2008b. Claw-free graphs V. Global structure. J. Combinat. Theory Ser B 98, 1373--1410.

Digital Library

[8]

M. Chudnovsky and P. Seymour. 2012. Claw-free graphs VII. Quasi-line graphs. J. Combinat. Theory Ser B 102, 1267--1294.

Digital Library

[9]

M. Chudnovsky, A. D. King, M. Plumettaz, and P. Seymour. 2013. A local strengthening of Reed’s ω, Δ, and χ conjecture for quasi-line graphs. SIAM J. Disc. Math. 27, 95--108.

[10]

A. Dubois, M. Rouire, and G. Stauffer (supervisor). 2011. Décomposition des graphes quasi-line et reduction du problem de couplage. Travail d’Etude et de Recherche à l’Université Bordeaux 2.

[11]

J. Edmonds. 1965. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stand. 69, 125--130.

[12]

F. Eisenbrand, G. Oriolo, G. Stauffer, and P. Ventura. 2008. The stable set polytope of quasi-line graphs. Combinatorica 28, 1, 45--67.

Digital Library

[13]

J. Fouquet. 1993. A strengthening of Ben Rebea’s lemma. J. Combinat. Theory 59, 35--40.

Digital Library

[14]

H. N. Gabow. 1990. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms.

Digital Library

[15]

H. Hemper and D. Kratsch. 2002. On claw-free asteroidal triple-free graphs. Disc. Appl. Math. 121, 155--180.

Digital Library

[16]

D. Hermelin, M. Mnich, E. J. Van Leeuwen, and G. J. Woeginger. 2011. Domination when the stars are out. In Proceedings of ICALP 2011. A. Lodi, A. Panconesi and G. Rinaldi Eds., 462--473.

Digital Library

[17]

W. S. Kennedy and A. D. King. 2011. Finding a smallest odd hole in a claw-free graph using global structure. arXiv:1103.6222.

[18]

A. D. King. 2009. Claw-free graphs and two conjectures on ω, Δ, and χ. Ph.D. Thesis, McGill University.

Digital Library

[19]

A. D. King and B. Reed. 2008. Bounding χ in terms of ω and Δ for quasi-line graphs. J. Graph Theory 59, 215--228.

Digital Library

[20]

A. D. King and B. Reed. 2012. Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Δ, and χ. http://arxiv.org/abs/1212.3036.

[21]

A. D. King and B. Reed. 2013. Asymptotics of the chromatic number for quasi-line graphs. J. Graph Theory 73, 327--341.

[22]

T. Kloks, D. Kratsch, and H. Müller. 2000. Finding and counting small induced subgraphs efficiently. Inf. Process. Lett. 74, 3--4, 115--121.

Digital Library

[23]

J. Krausz. 1943. Démonstration nouvelle d’un théorème de Whitney sur les réseaux. Mat. Fix. Lapok 50, 75--85.

[24]

L. Lovász, and M. D. Plummer. 1986. Matching Theory. North Holland, Amsterdam.

[25]

G. J. Minty. 1980. On maximal independent sets of vertices in claw-free graphs. J. Combinat. Theory 28, 284--304.

[26]

D. Nakamura and A. Tamura. 2001. A revision of Minty’s algorithm for finding a maximum weighted stable set of a claw-free graph. J. Oper. Res. Soc. Japan 44, 2, 194--204.

[27]

P. Nobili and A. Sassano. 2011. A reduction algorithm for the weighted stable set problem in claw-free graphs. In Proceedings of the 10th Cologne-Twente Workshop, 223--226.

[28]

G. Oriolo, U. Pietropaoli, and G. Stauffer. 2008. A new algorithm for the maximum weighted stable set problem in claw-free graphs. In Proceedings of the 13th IPCO Conference. A. Lodi, A. Panconesi, and G. Rinaldi Eds., 77--96.

Digital Library

[29]

G. Oriolo, U. Pietropaoli, and G. Stauffer. 2012. On the recognition of fuzzy circular interval graphs. Disc. Math. 312, 8, 1426--1435.

Digital Library

[30]

W. R. Pulleyblank and F. B. Shepherd. 1993. Formulations for the stable set polytope of a claw-free graph. In Proceedings of the 3rd IPCO Conference. G. Rinaldi and L. Wolsey Eds., 267--279.

[31]

N. D. Roussopoulos. 1973. A max m,n algorithm for determining the graph H from its line graph G. Inf. Proc. Lett. 2, 4, 108--112.

[32]

N. Sbihi. 1980. Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile. Disc. Math. 29, 53--76.

Digital Library

[33]

A. Schrijver. 2003. Combinatorial optimization. Polyhedra and efficiency (3 volumes). Algorithms and Combinatorics 24. Springer, Berlin, Germany.

Cited By

Ganesan A(2025)The Structure of Hypergraphs Arising in Cellular Mobile Communication SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2024.346017024:1(150-164)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TMC.2024.3460170
Faenza YFerrarini L(2024)The total matching polytope of complete bipartite graphsOperations Research Letters10.1016/j.orl.2024.10714456(107144)Online publication date: Sep-2024
https://doi.org/10.1016/j.orl.2024.107144
Jartoux B(2024)Counting kernels in directed graphs with arbitrary orientationsDiscrete Applied Mathematics10.1016/j.dam.2024.04.018355(62-73)Online publication date: Oct-2024
https://doi.org/10.1016/j.dam.2024.04.018
Show More Cited By

Index Terms

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Supereulerian graphs with small circumference and 3-connected hamiltonian claw-free graphs

A graph G is supereulerian if it has a spanning eulerian subgraph. We prove that every 3-edge-connected graph with the circumference at most 11 has a spanning eulerian subgraph if and only if it is not contractible to the Petersen graph. As applications,...
Local Clique Covering of Claw-Free Graphs

A k-clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a k-clique covering is called the local clique cover number of ...
The maximum 3-star packing problem in claw-free cubic graphs
Abstract
A 3-star is a complete bipartite graph $K_{1, 3}$ . A 3-star packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 3-star. The maximum 3-star packing problem is to find a 3-star packing of a given graph with ... $\frac{}{}$ $\frac{}{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 61, Issue 4

July 2014

259 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2660259

Editor:
Victor Vianu
University of California, San Diego

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2014

Accepted: 01 April 2014

Revised: 01 January 2014

Received: 01 August 2011

Published in JACM Volume 61, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Fondazione Cassa di Risparmio di Padova e Rovigo
Progetto di Eccellenza 2008–2009 of the Fondazione
Deutsche Forschungsgemeinschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
515
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ganesan A(2025)The Structure of Hypergraphs Arising in Cellular Mobile Communication SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2024.346017024:1(150-164)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TMC.2024.3460170
Faenza YFerrarini L(2024)The total matching polytope of complete bipartite graphsOperations Research Letters10.1016/j.orl.2024.10714456(107144)Online publication date: Sep-2024
https://doi.org/10.1016/j.orl.2024.107144
Jartoux B(2024)Counting kernels in directed graphs with arbitrary orientationsDiscrete Applied Mathematics10.1016/j.dam.2024.04.018355(62-73)Online publication date: Oct-2024
https://doi.org/10.1016/j.dam.2024.04.018
Cordasco GGargano LRescigno A(2024)Getting linear time in graphs of bounded neighborhood diversityNetworks10.1002/net.22232Online publication date: 7-Jun-2024
https://doi.org/10.1002/net.22232
Ganesan A(2023)Structured Hypergraphs in Cellular Mobile Communication SystemsProceedings of the 24th International Conference on Distributed Computing and Networking10.1145/3571306.3571335(188-196)Online publication date: 4-Jan-2023
https://dl.acm.org/doi/10.1145/3571306.3571335
Köse AKoca MAnarım EMédard M(2023)Age of Information Minimizing Dynamic User Pairing in Downlink NOMA Systems2023 IEEE International Mediterranean Conference on Communications and Networking (MeditCom)10.1109/MeditCom58224.2023.10266627(145-150)Online publication date: 4-Sep-2023
https://doi.org/10.1109/MeditCom58224.2023.10266627
Bianchi SEscalante MNasini GWagler A(2023)Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphsDiscrete Applied Mathematics10.1016/j.dam.2023.01.012332(70-86)Online publication date: Jun-2023
https://doi.org/10.1016/j.dam.2023.01.012
Kroger SValidi HHicks I(2023)A polytime preprocess algorithm for the maximum independent set problemOptimization Letters10.1007/s11590-023-02076-818:2(651-661)Online publication date: 24-Nov-2023
https://doi.org/10.1007/s11590-023-02076-8
Oriolo GStauffer G(2022)On the facets of stable set polytopes of circular interval graphsAnnals of Operations Research10.1007/s10479-021-04449-7312:2(1007-1029)Online publication date: 3-Mar-2022
https://doi.org/10.1007/s10479-021-04449-7
Çela EPunnen A(2022)Complexity and Polynomially Solvable Special Cases of QUBOThe Quadratic Unconstrained Binary Optimization Problem10.1007/978-3-031-04520-2_3(57-95)Online publication date: 9-Apr-2022
https://doi.org/10.1007/978-3-031-04520-2_3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents