Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull

详细信息    查看全文

• 作者：Andreas Brandst?dt ; Raffaele Mosca
• 关键词：Maximum weight independent set ; Clique separators ; Modular decomposition ; Polynomial time algorithm ; Hole ; free graphs
• 刊名：Graphs and Combinatorics
• 出版年：2015
• 出版时间：September 2015
• 年：2015
• 卷：31
• 期：5
• 页码：1249-1262
• 全文大小：471 KB
• 参考文献：1.Basavaraju, M., Chandran, L.S., Karthick, T.: Maximum weight independent sets in hole- and dart-free graphs. Discrete Appl. Math. 160, 2364-369 (2012)CrossRef MathSciNet MATH
  2.Berry, A., Bordat, J.-P., Heggernes, P.: Recognizing weakly triangulated graphs by edge separability. Nord. J. Comput. 7, 164-77 (2000)MathSciNet MATH
  3.Berry, A., Brandst?dt, A., Giakoumakis, V., Maffray, F.: Efficiently recognizing, decomposing and triangulating hole- and diamond-free graphs, manuscript 2012; accepted for Discrete Appl. Math. (2012)
  4.Brandst?dt, A.: (\(P_5\) , diamond)-free graphs revisited: structure and linear time optimization. Discrete Appl. Math. 138, 13-7 (2004)CrossRef MathSciNet MATH
  5.Brandst?dt, A., Giakoumakis, V.: Maximum weight independent sets in hole- and co-chair-free graphs. Inf. Process. Lett. 112, 67-1 (2012)CrossRef MATH
  6.Brandst?dt, A., Giakoumakis, V., Maffray, F.: Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. Discrete Appl. Math. 160, 471-78 (2012)CrossRef MathSciNet MATH
  7.Brandst?dt, A., Hoàng, C.T., Le, V.B.: Stability number of bull- and chair-free graphs revisited. Discrete Appl. Math. 131, 39-0 (2003)CrossRef MathSciNet MATH
  8.Brandst?dt, A., Klembt, T., Lozin, V.V., Mosca, R.: On independent vertex sets in subclasses of apple-free graphs. Algorithmica 56, 383-93 (2010)CrossRef MathSciNet MATH
  9.Brandst?dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Math. Appl., Vol. 3. SIAM, Philadelphia (1999)CrossRef MATH
  10.Chudnovsky, M.: The structure of bull-free graphs II and III—A summary, J. Comb. Theory Ser. B 102, 252-82 (2012)
  11.Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vuskovi?, K.: Recognizing Berge graphs. Combinatorica 25, 143-86 (2005)CrossRef MathSciNet MATH
  12.Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51-29 (2006)CrossRef MathSciNet MATH
  13.Chvátal, V., Fonlupt, J., Sun, L., Zemirline, A.: Recognizing dart-free perfect graphs. SIAM J. Comput. 31, 1315-338 (2002)CrossRef MathSciNet MATH
  14.Conforti, M., Cornuéjols, G., Liu, X., Vu?kovic, K., Zambelli, G.: Odd hole recognition in graphs of bounded clique size. SIAM J. Discrete Math. 20, 42-8 (2006)CrossRef MathSciNet MATH
  15.Cornuéjols, G., Liu, X., Vu?kovic, K.: A polynomial algorithm for recognizing perfect graphs. In: Procedings 44th annals of IEEE symposium on foundations of computer science FOCS 2003, pp. 20-7 (2003)
  16.De Simone, C.: On the vertex packing problem. Graphs Comb. 9, 19-0 (1993)CrossRef MATH
  17.De Simone, C., Sassano, A.: Stability number of bull- and chair-free graphs. Discrete Appl. Math. 9, 121-29 (1993)CrossRef
  18.De Figueiredo, C.M.H., Maffray, F., Porto, O.: On the structure of bull-free perfect graphs. Graphs Comb. 13, 31-5 (1997)CrossRef MATH
  19.Eschen, E.M., Sritharan, R.: A characterization of some graph classes with no long holes. J. Comb. Theory Ser. B 65, 156-62 (1995)CrossRef MathSciNet MATH
  20.Fricke, G.H., Hedetniemi, S.T., Jacobs, D.P.: Independence and irredundance in \(k\) -regular graphs. Ars Comb. 49, 271-79 (1998)MathSciNet MATH
  21.Fouquet, J.-L.: A decomposition for a class of \((P_5,{\overline{P_5}})\) -free graphs. Discrete Math. 121, 75-3 (1993)CrossRef MathSciNet MATH
  22.Gr?tschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Ann. Discrete Math. 21, 325-56 (1984)
  23.Hayward, R.B., Spinrad, J.B., Sritharan, R.: Improved algorithms for weakly chordal graphs, ACM Trans. Algorithms 3 (2007). Article 14
  24.McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201, 189-41 (1999)CrossRef MathSciNet MATH
  25.Mosca, R.: Some results on maximum stable sets in certain \(P_5\) -free graphs. Discrete Appl. Math. 132, 175-83 (2004)CrossRef MathSciNet
  26.Penev, I.: Forbidden substructures in graphs and trigraphs, and related coloring problems, PhD Thesis, Columbia University (2012)
  27.Spinrad, J.P.: Finding large holes. Inf. Process. Lett. 39, 227-29 (1991)CrossRef MathSciNet MATH
  28.Spinrad, J.P., Sritharan, R.: Algorithms for weakly triangulated graphs. Discrete Appl. Math. 59, 181-91 (1995)CrossRef MathSciNet MATH
  29.Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55, 221-32 (1985)CrossRef MathSciNet MATH
  30.Thomassé, S., Trotignon, N., Vuskovi?, K.: Parameterized algorithm for weighted independent set problem in bull-free graphs, Technical report 2013; available online
  31.Vuskovi?, K.:Personal communication
  32.Whitesides, S.H.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. In: Berge, C., Chvátal, V. (eds.) Topics on Perfect Graphs. North-Holland, Amsterdam (1984)
  
• 作者单位：Andreas Brandst?dt (1)
  Raffaele Mosca (2)
  
  1. Institut für Informatik, Universit?t Rostock, 18051, Rostock, Germany
  2. Dipartimento di Economia, Universitá degli Studi “G. d’Annunzio- 65121, Pescara, Italy
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

The maximum weight independent set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be NP-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying clique separator decomposition as well as modular decomposition, we obtain polynomial time solutions of MWIS for odd-hole- and dart-free graphs as well as for odd-hole- and bull-free graphs (dart and bull have five vertices, say \(a,b,c,d,e\), and dart has edges \(ab,ac,ad,bd,cd,de\), while bull has edges \(ab,bc,cd,be,ce\)). If the graphs are hole-free instead of odd-hole-free then stronger structural results and better time bounds are obtained. Keywords Maximum weight independent set Clique separators Modular decomposition Polynomial time algorithm Hole-free graphs