The Library

Independent sets of maximum weight in apple-free graphs

Tools

Brandstädt, Andreas, Lozin, Vadim V. and Mosca, Raffaele. (2010) Independent sets of maximum weight in apple-free graphs. SIAM Journal on Discrete Mathematics, Vol.24 (No.1). pp. 239-254. ISSN 0895-4801

PDF
WRAP_Lozin_independent_sets.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (284Kb)

Official URL: http://dx.doi.org/10.1137/090750822

Abstract

We present the first polynomial-time algorithm to solve the maximum weight independent set problem for apple-free graphs, which is a common generalization of several important classes where the problem can be solved efficiently, such as claw-free graphs, chordal graphs, and cographs. Our solution is based on a combination of two algorithmic techniques (modular decomposition and decomposition by clique separators) and a deep combinatorial analysis of the structure of apple-free graphs. Our algorithm is robust in the sense that it does not require the input graph G to be apple-free; the algorithm either finds an independent set of maximum weight in G or reports that G is not apple-free.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Graph algorithms, Combinatorial analysis
Journal or Publication Title:	SIAM Journal on Discrete Mathematics
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0895-4801
Date:	2010
Volume:	Vol.24
Number:	No.1
Number of Pages:	16
Page Range:	pp. 239-254
Identification Number:	10.1137/090750822
Status:	Peer Reviewed
Access rights to Published version:	Open Access
Funder:	University of Warwick. Centre for Discrete Mathematics and Its Applications
References:	[1] C. Berge, Two theorems in graph theory, Proc. Nat. Acad. Sci. USA, 43 (1957), pp. 842–844. [2] A. Brandst¨adt and C. T. Ho`ang, On clique separators, nearly chordal graphs, and the maximum weight stable set problem, Theoret. Comput. Sci., 389 (2007), pp. 295–306. [3] A. Brandst¨adt, T. Klembt, V. V. Lozin, and R. Mosca, Independent sets of maximum weight in apple-free graphs, Lecture Notes in Comput. Sci. 5369, 2008, pp. 849–859. [4] A. Brandst¨adt, T. Klembt, V. V. Lozin, and R. Mosca, On independent vertex sets in subclasses of apple-free graphs, Algorithmica, 56 (2010), pp. 383–393. [5] A. Brandst¨adt, V. B. Le, and S. Mahfud, New applications of clique separator decomposition for the maximum weight stable set problem, Theoret. Comput. Sci., 370 (2007), pp. 229–239. [6] A. Brandst¨adt, V. B. Le, and J. P. Spinrad, Graph Classes: A Survey, SIAM Monogr. Discrete Math. Appl., Vol. 3, SIAM, Philadelphia, 1999. [7] M. Chudnovsky and P. Seymour, Claw-free graphs. I—Orientable prismatic graphs, J. Combin. Theory Ser. B, 97 (2007), pp. 867–903. [8] M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a claw-free graph, J. Combin. Theory Ser. B, 97 (2007), pp. 350–357. [9] M. Chudnovsky and P. Seymour, Claw-free graphs. II—Nonorientable prismatic graphs, J. Combin. Theory Ser. B, 98 (2008), pp. 249–290. [10] M. Chudnovsky and P. Seymour, Claw-free graphs. III—Circular interval graphs, J. Combin. Theory Ser. B, 98 (2008), pp. 812–834. [11] M. Chudnovsky and P. Seymour, Claw-free graphs. IV—Decomposition theorem, J. Combin. Theory Ser. B, 98 (2008), pp. 839–938. [12] M. Chudnovsky and P. Seymour, Claw-free graphs. V—Global structure, J. Combin. Theory Ser. B, 98 (2008), pp. 1373–1410. [13] M. Chudnovsky and P. Seymour, Claw-free graphs. VI—The structure of quasi-line graphs, submitted. [14] M. Chudnovsky and P. Seymour, Claw-free graphs. VII—Coloring claw-free graphs, submitted. [15] D. G. Corneil, H. Lerchs, and L. K. Stewart, Complement reducible graphs, Discrete Appl. Math., 3 (1981), pp. 163–174. [16] C. De Simone, On the vertex packing problem, Graphs Combin., 9 (1993), pp. 19–30. [17] J. Edmonds, Paths, trees and flowers, Canad. J. Math., 17 (1965), pp. 449–467. [18] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B, 69B (1965), pp. 125–130. [19] R. Faudree, E. Flandrin, and Z. Ryj´aˇcek, Claw-free graphs—a survey, Discrete Math., 164 (1997), pp. 87–147. [20] A. Frank, Some polynomial algorithms for certain graphs and hypergraphs, in Proceedings of the Fifth British Combinatorial Conference (University of Aberdeen, Aberdeen 1975), Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Manitoba, 1976, pp. 211– 226. [21] F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., 1 (1972), pp. 180– 187. [22] M. U. Gerber and V. V. Lozin, Robust algorithms for the stable set problem, Graphs Combin., 19 (2003), pp. 347–356. [23] M. C. Golumbic, Algorithmic graph theory and perfect graphs, 2nd ed., Ann. Discrete Math. 57, Elsevier Science B.V., Amsterdam, 2004. [24] L. Lov´asz and M. D. Plummer, Matching Theory, Ann. Discrete Math. 29, North–Holland, Amsterdam, 1986. [25] V. V. Lozin, Stability in P5- and banner-free graphs, European J. Oper. Res., 125 (2000), pp. 292–297. [26] V. V. Lozin and M. Milaniˇc, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, J. Discrete Algorithms, 6 (2008), pp. 595–604. [27] G. J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B, 28 (1980), pp. 284–304. [28] D. Nakamura and A. Tamura, A revision of Minty’s algorithm for finding a maximum weight stable set of a claw-free graph, J. Oper. Res. Soc. Japan, 44 (2001), pp. 194–204. [29] S. Olariu, The strong perfect graph conjecture for pan-free graphs, J. Combin. Theory Ser. B, 47 (1989), pp. 187–191. [30] N. Sbihi, Algorithme de recherche d’un stable de cardinalit´e maximum dans un graphe sans ´etoile, Discrete Math., 29 (1980), pp. 53–76. [31] J. P. Spinrad, Efficient Graph Representations, Fields Inst. Monogr. 19, AMS, Providence, RI, 2003. [32] R. E. Tarjan, Decomposition by clique separators, Discrete Math., 55 (1985), pp. 221–232. [33] S. H. Whitesides, A method for solving certain graph recognition and optimization problems, with applications to perfect graphs, in Topics on Perfect Graphs, C. Berge and V. Chv´atal, eds., North–Holland Math. Stud. 88, North–Holland, Amsterdam, 1984, pp. 281–297.
URI:	http://wrap.warwick.ac.uk/id/eprint/3314