Algorithms for finding an independent $\{K_1,K_2\}$-packing of maximum weight in a graph

V. V. Lepin

Trudy Instituta matematiki, Tome 22 (2014) no. 1, pp. 78-97.

Résumé

Let $\mathcal{H}$ be a fixed set of connected graphs. A $\mathcal{H}$-packing of a given graph $G$ is a pairwise vertex-disjoint set of subgraphs of $G,$ each isomorphic to a member of $\mathcal{H}$. An independent $\mathcal{H}$-packing of a given graph $G$ is an $\mathcal{H}$-packing of $G$ in which no two subgraphs of the packing are joined by an edge of $G$. Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{N}$ and an edge weight function and $\omega_E:~E(G)\to\mathbb{N}$. Weight of an independent $\{K_1,K_2\}$-packing $S$ in $G$ is $\sum_{v\in U}\omega_V(v)+\sum_{e\in F}\omega_E(e),$ where $U=\bigcup_{G_i\in\mathcal{S},~G_i\cong K_1}V(G_i),$ and $F=\bigcup_{G_i\in\mathcal{S}}E(G_i)$. The problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight is considered. We present algorithms to solve this problem for trees in time $O(n)$, for unicyclic graphs in time $O(n^2)$, and cographs and thin spider graphs in time $O(n+m)$, for co-gem-free graphs in time $O(m(m+n))$, where $n$ and $m$ are the number of vertices and edges in the graph. Moreover, we give a robust $O(m(m+n))$ time algorithm solving this problem for the graph class $\mathcal{T}\cup\mathcal{U}\cup\mathcal{G}_1\cup\mathcal{G}_2\cup\mathcal{G}_3$, where $\mathcal{T}$ — trees, $\mathcal{U}$ — unicycle, $\mathcal{G}_1$ — (bull,fork)-free, $\mathcal{G}_2$ — (co-P,fork)-free, $\mathcal{G}_3$ — ($P_5,$fork)-free graphs.

Bibliographie

[1] Hell P., Kirkpatrick D. G., “On the complexity of general graph factor problems”, SIAM J. Computing, 12 (1983), 601–609 | DOI

[2] Caprara A., Rizzi R., “Packing triangles in bounded degree graphs”, Inform. Process. Lett., 84:4 (2002), 175–180 | DOI

[3] Guruswami V., Pandu Rangan C., Chang M. S., Chang G. J., Wong C. K., “The $K_r$-packing problem”, Computing, 66 (2001), 79–89 | DOI

[4] Cornuéjols G., Hartvigsen D., Pulleyblank W. R., “Packing subgraphs in a graph”, Operations Research Letters, 1 (1982), 139–143 | DOI

[5] Hartvigsen D., Hell P., Szabó J., “The $k$-piece packing problem”, J. Graph Theory, 52 (2006), 267–293 | DOI

[6] Hell P., “Packing in graphs”, Electronic Notes in Discrete Mathematics, 5 (2000) http://www.elsevier.nl | DOI

[7] Hell P., Kirkpatrick D. G., “Packings by cliques and by finite families of graphs”, Discrete Mathematics, 49 (1984), 118–133 | DOI

[8] Loebl M., Poljak S., “Efficient subgraph packing”, J. Combinatorial Theory. Ser. B, 59 (1993), 106–121 | DOI

[9] Kloks T., Poon S.-H., Some results on triangle partitions, 2011, 18 pp., arXiv: 1104.3919

[10] Cameron K., Hell P., “Independent packings in structured graphs”, Math. Program. Ser. B, 105 (2006), 201–213 | DOI

[11] Cameron K., “Brambles and independent packings in chordal graphs”, Discr. Math., 309:18 (2009), 5766–5769 | DOI

[12] Lepin V. V., “Lineinyi algoritm dlya nakhozhdeniya maksimalnogo indutsirovannogo parosochetaniya naimenshego vesa v reberno-vzveshennom dereve”, Trudy Instituta matematiki NAN Belarusi, 15:1 (2007), 78–90

[13] Cameron K., “Induced matchings”, Discrete Applied Mathematics, 24 (1989), 97–102 | DOI

[14] Cameron K., “Induced matchings in intersection graphs”, Discrete Mathematics, 278 (2003), 1–9 | DOI

[15] Cameron K., Sritharan R., Tang Y., “Finding a maximum induced matching in weakly chordal graphs”, Discrete Mathematics, 266 (2003), 133–142 | DOI

[16] Chalermsook P., Laekhanukit B., Nanongkai D., “Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More”, SODA, 13 (2013), 1557–1576

[17] Chang J.-M., “Induced matchings in asteroidal-triple free graphs”, Discrete Applied Mathematics, 132 (2003), 67–78 | DOI

[18] Duckworth W., Wormald N. C., Zito M., “Maximum induced matchings of random cubic graphs”, J. Computational and Applied Mathematics, 142 (2002), 39–50 | DOI

[19] Faudree R. J., Gyárfás A., Schelp R. H., Tuza Zs., “Induced matchings in bipartite graphs”, Discrete Mathematics, 78 (1989), 83–87 | DOI

[20] Fricke G., Laskar R. C., “Strong matchings on trees”, Congressus Numerantium, 89 (1992), 239–243

[21] Gavril F., “Maximum induced multicliques and complete multipartite subgraphs in polygon-circle graphs and circle graphs”, Graph-Theoretic Concepts in Computer Science, Springer, Berlin–Heidelberg, 2012, 297–307 | DOI

[22] Golumbic M. C., Laskar R. C., “Irredundancy in circular-arc graphs”, Discrete Applied Mathematics, 44 (1993), 79–89 | DOI

[23] Golumbic M. C., Lewenstein M., “New results on induced matchings”, Discrete Applied Mathematics, 101 (2000), 157–165 | DOI

[24] Hermelin D., Mnich M., van Leeuwen E. J., “Parameterized complexity of induced h-matching on claw-free graphs”, Algorithms-ESA 2012, Springer, Berlin–Heidelberg, 2012, 624–635 | DOI

[25] Hermelin D., Mnich M., van Leeuwen E. J., “Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs”, Algorithmica, 2014, 1–48

[26] Horák P., He Q., Trotter W. T., “Induced matchings in cubic graphs”, J. Graph Theory, 17 (1993), 151–160 | DOI

[27] 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 (2003), 327–346 | DOI

[28] Lepin V. V., “A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree”, Electronic Notes in Discrete Mathematics, 24 (2006), 111–116 | DOI

[29] Lozin V. V., “On maximum induced matchings in bipartite graphs”, Information Processing Letters, 81 (2002), 7–11 | DOI

[30] Stockmeyer L. J., Vazirani V. V., “NP-completeness of some generalizations of the maximum matching problem”, Information Processing Letters, 15 (1982), 14–19 | DOI

[31] Ko C. W., Shepherd F. B., “Bipartite domination and simultaneous matroid covers”, SIAM J. Discrete Mathematics, 16 (2003), 327–349

[32] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V., “NP-hard graph problems and boundary classes of graphs”, Theor. Comp. Science, 389:1–2 (2007), 219–236 | DOI

[33] Boliac R., Cameron K., Lozin V. V., “On computing the dissociation number and the induced matching number of bipartite graphs”, Ars Comb., 72 (2004), 241–253

[34] Kardos F., Katrenic J., Schiermeyer I., “On computing the minimum 3-path vertex cover and dissociation number of graphs”, Theoretical Computer Science, 412:50 (2011), 7009–7017 | DOI

[35] Lozin V. V., Rautenbach D., “Some results on graphs without long induced paths”, Inf. Process. Lett., 88:4 (2003), 167–171 | DOI

[36] Orlovich Y., Dolgui A., Finke G., Gordon V., Werner F., “The complexity of dissociation set problems in graphs”, Discrete Applied Mathematics, 159:13 (2011), 1352–1366 | DOI

[37] Yannakakis M., “Node-deletion problems on bipartite graphs”, SIAM J. Computing, 10 (1981), 310–327 | DOI

[38] Frank A., “Some polynomial algorithms for certain graphs and hypergraphs”, Proc. of the 5th Brit. Comb. Conf. (Aberdeen, 1975), Congr. Numer., XV, 1976, 211–226

[39] Corneil D. G., Perl Y., Stewart L. K., “A Linear Recognition Algorithm for Cographs”, SIAM Journal on Computing, 14:4 (1985), 926–934 | DOI

[40] Habib M., Paul C., “A simple linear time algorithm for cograph recognition”, Discrete Applied Mathematics, 145:2 (2005), 183–197 | DOI

[41] Gallai T., “Transitiv orienterbare graphe”, Acta Math. Acad. Sci. Hungar., 18 (1967), 25–66 | DOI

[42] Habib M., Maurer M. C., “On the X-join decomposition of undirected graphs”, Discrete Applied Mathematics, 1 (1979), 201–207 | DOI

[43] James L. O., Stanton R. G., Cowan D. D., “Graph decomposition for undirected graphs”, Proc. of the third Southeastern International Conference on Combinatorics, Graph Theory, and Computing, CGTC'72, 1972, 281–290

[44] Cournier A., Habib M., “A New Linear Algorithm for Modular Decomposition”, Proc. of Trees in Algebra and Programming, CAAP'94, LNCS, 787, 1994, 68–84

[45] McConnell R. M., Spinrad J. P., “Modular decomposition and transitive orientation”, Discr. Math., 201 (1999), 189–241 | DOI

[46] Tedder M., Corneil D., Habib M., Paul C., “Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations”, Proc. Int. Colloq. Automata, Languages and Programming, ICALP 2008, Lecture Notes in Computer Science, 5125, Springer-Verlag, 2008, 634–645 | DOI

[47] Brandstadt A., Ho`ang C. T., Le V. B., “Stability number of bull- and chair-free graphs revisited”, Discrete Applied Math., 131 (2003), 39–50 | DOI

[48] Brandstadt A., Le V. B., de Ridder H. N., “Efficient robust algorithms for the Maximum Weight Stable Set Problem in chair-free graph classes”, Inf. Process. Lett., 89 (2004), 165–173 | DOI