Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bertossi A.A., Moretti S.: Parallel algorithms on circular-arc graphs, Information Processing Letters 33, 275–281 (1990)
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)
Brandstädt A., Le V.B., Jeremy P. Spinrad, Graph Classes - A Survey, SIAM Publications, Philadelphia, PA, 1999
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)
Kathie Cameron, Induced matchings. Discrete Applied Mathematics 24, 97–102 (1989)
Kathie Cameron, Induced matchings in intersection graphs. Discrete Mathematics 278, 1–9 (2003)
Cameron, K., Sritharan, R., Tang, Y., Finding a maximum induced matching in weakly chordal graphs. Discrete Mathematics 266, 133–142 (2003)
Cameron K., Walker, T.L., The graphs with maximum matching and maximum induced matching the same size, accepted for publication in Discrete Mathematics
Jou-Ming Chang, Induced matchings in asteroidal-triple free graphs. Discrete Applied Mathematics 132, 67–78 (2003)
Cornuéjols, G., Hartvigsen, D., Pulleyblank, W.R., Packing subgraphs in a graph. Operations Research Letters 1, 139–143 (1982)
Duckworth, W., Wormald, N.C., Zito, M., Maximum induced matchings of random cubic graphs. J Computational and Applied Mathematics 142, 39–50 (2002)
Faudree, R.J., Gyárfás, A., Schelp, R.H., Tuza, Zs., Induced matchings in bipartite graphs. Discrete Mathematics 78, 83–87 (1989)
Fricke G., Laskar, R.C., Strong matchings on trees. Congressus Numerantium 89, 239–243 (1992)
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
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)
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)
Gavril, F.: Algorithms on circular-arc graphs. Networks 4, 357–369 (1974)
Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Information Processing Letters 73, 181–188 (2000)
Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and interval graphs. Canadian J Mathematics 16, 539–548 (1964)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980
Golumbic, M.C., Hammer, P.L.: Stability in circular arc graphs. J Algorithms 9, 314–320 (1988)
Golumbic, M.C., Laskar, R.C.: Irredundancy in circular-arc graphs. Discrete Applied Mathematics 44, 79–89 (1993)
Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Applied Mathematics 101, 157–165 (2000)
Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discrete Mathematics 43, 37–46 (1983)
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
Guruswami, V., Pandu Rangan, C., Chang, M.S., Chang, G.J., Wong, C.K.: The K r -packing problem. Computing 66, 79–89 (2001)
Hartvigsen, D., Hell, P., Szabó, J.: The k-piece packing problem, submitted
Hayward, R.B.: Weakly triangulated graphs. J Combinatorial Theory Series B 39, 200–209 (1985)
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)
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)
Hell, P.: Packing in graphs. Electronic Notes in Discrete Mathematics 5, (http://www.elsevier.nl) (2000)
Hell, P., Kirkpatrick, D.G.: On the complexity of general graph factor problems. SIAM J Computing 12, 601–609 (1983)
Hell, P., Kirkpatrick, D.G.: Packings by cliques and by finite families of graphs. Discrete Mathematics 49, 118–133 (1984)
Hell, P., Klein, S., Protti, F., Tito, L.: On generalized split graphs. Electronic Notes in Discrete Mathematics 7, (http://www.elsevier.com) (2001)
Hell, P., Klein, S., Tito-Nogueira, L., Protti, F.: Independent K r 's in chordal graphs. XI Latin-Iberian American Congress of Operations Research, CLAIO2002
Hell, P., Klein, S., Tito-Nogueira, L., Protti, F.: Partitioning chordal graphs into independent sets and cliques. Discrete Applied Mathematics 141, 185–194 (2004)
Hell, P., Klein, S. Tito-Nogueira, L., Protti, F.: Packing r-cliques in weighted chordal graphs, accepted for publication in Annals of Operations Research
Horák, P., He, Q., Trotter, W.T.: Induced matchings in cubic graphs. J Graph Theory 17, 151–160 (1993)
Janson, S., Kratochvíl, J.: Threshold functions for classes of intersection graphs. Discrete Mathematics 108, 307–326 (1992)
Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid covers. SIAM J Discrete Mathematics 16, 327–349 (2003)
Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and P 5-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37, 327–346 (2003)
Köhler, E.G.: Graphs Without Asteroidal Triples, PhD thesis, Technical University of Berlin, Cuvillier Verlag, Göttingen, 1999
Kostochka, A., Kratochvíl, J.: Covering and coloring polygon-circle graphs. Discrete Mathematics 163, 299–305 (1997)
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)
Loebl, M., Poljak, S.: Efficient subgraph packing. J Combinatorial Theory Series B 59, 106–121 (1993)
Lozin, V.V.: On maximum induced matchings in bipartite graphs. Information Processing Letters 81, 7–11 (2002)
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)
Spinrad, J.P., Sritharan, R.: Algorithms for weakly triangulated graphs. Discrete Applied Mathematics 19, 181–191 (1995)
Srinivasa Rao, A., Pandu Rangan, C.: Optimal parallel algorithms on circular-arc graphs. Information Processing Letters 33, 147–156 (1989)
Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters 15, 14–19. (1982)
Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J Computing 10, 310–327 (1981)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of both authors is supported by the Natural Sciences and Engineering Research Council of Canada.
Rights and permissions
About this article
Cite this article
Cameron, K., Hell, P. Independent packings in structured graphs. Math. Program. 105, 201–213 (2006). https://doi.org/10.1007/s10107-005-0649-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0649-5
Keywords
- Independent set
- Induced matching
- Chordal graph
- Circular-arc graph
- Polygon-circle graph
- Cocomparability graph
- Interval-filament graph
- Intersection graph
- Asteroidal triple-free graph
- Weakly chordal graph
- Chordal bipartite graph
- Dissociation set