×

Independent packings in structured graphs. (English) Zbl 1078.05067

Summary: Packing a maximum number of disjoint triangles into a given graph \(G\) is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertossi A.A., Moretti S.: Parallel algorithms on circular-arc graphs, Information Processing Letters 33, 275–281 (1990) · Zbl 0696.68049
[2] Boliac R., Cameron K., Lozin V.: On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combinatoria 72, 241–253 (2004) · Zbl 1075.05066
[3] Brandstädt A., Le V.B., Jeremy P. Spinrad, Graph Classes - A Survey, SIAM Publications, Philadelphia, PA, 1999 · Zbl 0919.05001
[4] Broersma, H.J., Kloks, T., Kratsch, D., Müller, H., Independent sets in asteroidal triple-free graphs. SIAM J Discrete Mathematics 12, 276–287 (1999) · Zbl 0918.68072
[5] Kathie Cameron, Induced matchings. Discrete Applied Mathematics 24, 97–102 (1989)
[6] Kathie Cameron, Induced matchings in intersection graphs. Discrete Mathematics 278, 1–9 (2003) · Zbl 1024.05501
[7] Cameron, K., Sritharan, R., Tang, Y., Finding a maximum induced matching in weakly chordal graphs. Discrete Mathematics 266, 133–142 (2003) · Zbl 1022.05064
[8] Cameron K., Walker, T.L., The graphs with maximum matching and maximum induced matching the same size, accepted for publication in Discrete Mathematics · Zbl 1073.05054
[9] Jou-Ming Chang, Induced matchings in asteroidal-triple free graphs. Discrete Applied Mathematics 132, 67–78 (2003) · Zbl 1029.05120
[10] Cornuéjols, G., Hartvigsen, D., Pulleyblank, W.R., Packing subgraphs in a graph. Operations Research Letters 1, 139–143 (1982) · Zbl 0488.90070
[11] Duckworth, W., Wormald, N.C., Zito, M., Maximum induced matchings of random cubic graphs. J Computational and Applied Mathematics 142, 39–50 (2002) · Zbl 1001.05093
[12] Faudree, R.J., Gyárfás, A., Schelp, R.H., Tuza, Zs., Induced matchings in bipartite graphs. Discrete Mathematics 78, 83–87 (1989) · Zbl 0709.05026
[13] Fricke G., Laskar, R.C., Strong matchings on trees. Congressus Numerantium 89, 239–243 (1992) · Zbl 0786.05065
[14] Gallai, T.: Transitiv orientierbare Graphen (German). Acta Mathematica Academiae Scientiarum Hungaricae 18 (1967), 25-66. English translation by F. Maffray and M. Preissmann in Perfect Graphs, J.L. Ramírez Alfonsín and B.A. Reed, eds., John Wiley and Sons, Chichester, 2001 · Zbl 0153.26002
[15] Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitiou, C.H., The complexity of coloring circular arcs and chords. SIAM J Algebraic and Discrete Methods 1, 216–227 (1980) · Zbl 0499.05058
[16] Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J Computing 1, 180–187 (1972) · Zbl 0227.05116
[17] Gavril, F.: Algorithms on circular-arc graphs. Networks 4, 357–369 (1974) · Zbl 0309.05126
[18] Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Information Processing Letters 73, 181–188 (2000) · Zbl 1339.05287
[19] Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and interval graphs. Canadian J Mathematics 16, 539–548 (1964) · Zbl 0121.26003
[20] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980 · Zbl 0541.05054
[21] Golumbic, M.C., Hammer, P.L.: Stability in circular arc graphs. J Algorithms 9, 314–320 (1988) · Zbl 0651.68083
[22] Golumbic, M.C., Laskar, R.C.: Irredundancy in circular-arc graphs. Discrete Applied Mathematics 44, 79–89 (1993) · Zbl 0783.05059
[23] Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Applied Mathematics 101, 157–165 (2000) · Zbl 0951.68104
[24] Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discrete Mathematics 43, 37–46 (1983) · Zbl 0502.05050
[25] Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Topics on perfect graphs, 325–356, North-Holland Math. Stud., 88, North-Holland, Amsterdam, 1984 · Zbl 0554.05041
[26] Guruswami, V., Pandu Rangan, C., Chang, M.S., Chang, G.J., Wong, C.K.: The Kr-packing problem. Computing 66, 79–89 (2001) · Zbl 0978.05060
[27] Hartvigsen, D., Hell, P., Szabó, J.: The k-piece packing problem, submitted · Zbl 1099.05066
[28] Hayward, R.B.: Weakly triangulated graphs. J Combinatorial Theory Series B 39, 200–209 (1985) · Zbl 0551.05055
[29] Hayward, R.B., Hoàng, C.T., Maffray, F.: Optimizing weakly triangulated graphs. Graphs and Combinatorics 5, 339-349 (1989); erratum in 6, 33–35 (1990) · Zbl 0679.68082
[30] Hayward, R.B., Spinrad, J.P., Sritharan, R.: Weakly chordal graph algorithms via handles. Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 42–49 (2000) · Zbl 0956.68104
[31] Hell, P.: Packing in graphs. Electronic Notes in Discrete Mathematics 5, (http://www.elsevier.nl) (2000) · Zbl 0944.05037
[32] Hell, P., Kirkpatrick, D.G.: On the complexity of general graph factor problems. SIAM J Computing 12, 601–609 (1983) · Zbl 0525.68023
[33] Hell, P., Kirkpatrick, D.G.: Packings by cliques and by finite families of graphs. Discrete Mathematics 49, 118–133 (1984) · Zbl 0582.05046
[34] Hell, P., Klein, S., Protti, F., Tito, L.: On generalized split graphs. Electronic Notes in Discrete Mathematics 7, (http://www.elsevier.com) (2001) · Zbl 0981.05076
[35] Hell, P., Klein, S., Tito-Nogueira, L., Protti, F.: Independent Kr’s in chordal graphs. XI Latin-Iberian American Congress of Operations Research, CLAIO2002 · Zbl 1043.05097
[36] Hell, P., Klein, S., Tito-Nogueira, L., Protti, F.: Partitioning chordal graphs into independent sets and cliques. Discrete Applied Mathematics 141, 185–194 (2004) · Zbl 1043.05097
[37] Hell, P., Klein, S. Tito-Nogueira, L., Protti, F.: Packing r-cliques in weighted chordal graphs, accepted for publication in Annals of Operations Research · Zbl 1091.90073
[38] Horák, P., He, Q., Trotter, W.T.: Induced matchings in cubic graphs. J Graph Theory 17, 151–160 (1993) · Zbl 0787.05038
[39] Janson, S., Kratochvíl, J.: Threshold functions for classes of intersection graphs. Discrete Mathematics 108, 307–326 (1992) · Zbl 0769.05084
[40] Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid covers. SIAM J Discrete Mathematics 16, 327–349 (2003) · Zbl 1029.05097
[41] Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and P5-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37, 327–346 (2003) · Zbl 1082.68592
[42] Köhler, E.G.: Graphs Without Asteroidal Triples, PhD thesis, Technical University of Berlin, Cuvillier Verlag, Göttingen, 1999 · Zbl 1118.05090
[43] Kostochka, A., Kratochvíl, J.: Covering and coloring polygon-circle graphs. Discrete Mathematics 163, 299–305 (1997) · Zbl 0871.05025
[44] Lekkerkerker, C.G., Boland, J.Ch.: Representation of a finite graph by a set of intervals on the line. Fundamenta Mathematicae 51, 45–64 (1962) · Zbl 0105.17501
[45] Loebl, M., Poljak, S.: Efficient subgraph packing. J Combinatorial Theory Series B 59, 106–121 (1993) · Zbl 0794.05105
[46] Lozin, V.V.: On maximum induced matchings in bipartite graphs. Information Processing Letters 81, 7–11 (2002) · Zbl 1046.68081
[47] Naor, J., Naor, M., Schäeffer, A.A.: Fast parallel algorithms for chordal graphs. Proceedings 19th Annual ACM Symposium on Theory of Computing, 355–364 (1987)
[48] Spinrad, J.P., Sritharan, R.: Algorithms for weakly triangulated graphs. Discrete Applied Mathematics 19, 181–191 (1995) · Zbl 0827.68084
[49] Srinivasa Rao, A., Pandu Rangan, C.: Optimal parallel algorithms on circular-arc graphs. Information Processing Letters 33, 147–156 (1989) · Zbl 0688.68046
[50] Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters 15, 14–19. (1982) · Zbl 0493.68039
[51] Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J Computing 10, 310–327 (1981) · Zbl 0468.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.