Some cases of the polynomial solvability of the problem of findingan independent $\{K_1,K_2\}$-packing of maximum weight in a graph

V. V. Lepin

Trudy Instituta matematiki, Tome 24 (2016) no. 2, pp. 72-90.

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_{H\in\mathcal{S},~H\cong K_1}V(H),$ and $F=\bigcup_{H\in\mathcal{S}}E(H).$ The problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight is considered. Let $C(G_1,\ldots ,G_{|V(C)|})$ denote a graph formed from a labelled graph $C$ and unlabelled graphs $G_1,\ldots ,G_{|V(C)|},$ replacing every vertex $v_i\in V(C)$ by the graph $G_i,$ and joining the vertices of $V(G_i)$ with all the vertices of those of $V(G_j),$ whenever $v_iv_j\in E(C).$ For unlabelled graphs $C,G_1,\ldots ,G_{|V(C)|},$ let $\Phi_C(G_1,\ldots ,G_{|V(C)|})$ stand for the class of all graphs $C(G_1,\ldots ,G_{|V(C)|})$ taken over all possible orderings of $V(C).$ Let $\mathcal{B,C}$ be classes of prime graphs such that $K_1\in \mathcal{B}\backslash \mathcal{C}.$ A prime inductive class of graphs, $I(\mathcal{B,C}),$ is defined inductively as follows: (1) all graphs from $\mathcal{B}$ belong to $I(\mathcal{B,C}),$ (2) if $C\in \mathcal{C}$ and $\{G_1,\ldots ,G_{|V(C)|}\}\subseteq$ $\subseteq I(\mathcal{B,C}),$ then all graphs from $\Phi_C(G_1,\ldots ,G_{|V(C)|})$ belong to $I(\mathcal{B,C}).$ We present a robust $O(m(m+n))$ time algorithm solving this problem for the graph class $I(\{K_1\}, \mathcal{G}_1\cup \mathcal{G}_2\cup \mathcal{G}_3\cup \mathcal{G}_4),$ where $\mathcal{G}_1$ — prime split graphs, $\mathcal{G}_2$ — prime trees, $\mathcal{G}_3$ — prime unicycle, $\mathcal{G}_3$ — prime co-gem-free graphs.

Bibliographie

[1] Lepin V.V., “Algoritmy dlya nakhozhdeniya nezavisimoi $\{K_1,K_2\}$-upakovki naibolshego vesa v grafe”, Trudy Instituta matematiki, 22:1 (2014), 78–97 | Zbl

[2] Lepin V.V., “Reshenie zadachi o vzveshennoi nezavisimoi $\{K_1,K_2\}$-upakovke na grafakh s ogranichennoi drevesnoi shirinoi”, Trudy Instituta matematiki, 23:1 (2015), 98–114 | Zbl

[3] Lepin V.V., “Reshenie zadachi o vzveshennoi nezavisimoi $\{K_1,K_2\}$-upakovke na grafakh so spetsialnymi blokami”, Trudy Instituta matematiki, 23:2 (2015), 62–71

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

[5] 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 | MR | Zbl

[6] 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 | MR | Zbl

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

[8] 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 | MR | Zbl

[9] Jamison B., Olariu S., “A tree representation for $P_4$-sparse graphs”, Discrete Applied Mathematics, 35:2 (1992), 115–129 | DOI | MR | Zbl

[10] Jamison B., Olariu S., “$P_4$-reducible graphs, a class of uniquely tree representable graphs”, Studies in Applied Mathematics, 81 (1989), 79–87 | DOI | MR | Zbl

[11] Hoang C.T., A class of perfect graphs, Master's Thesis, School of Computer Science, McGill University, Montreal, 1983 | MR

[12] Jamison B., Olariu S., “On a unique tree representation for P4-extendible graphs”, Discrete Appl. Math., 34 (1991), 151–164 | DOI | MR | Zbl

[13] Giakoumakis V., Vanherpe J.-M., “On extended $P_4$-reducible and extended $P_4$-sparse graphs”, Theor. Comp. Sci., 180 (1997), 269–286 | DOI | MR | Zbl

[14] Jamison B., Olariu S., “A new class of brittle graphs”, Studies in Appl. Math., 81 (1989), 89–92 | DOI | MR | Zbl

[15] Maffray F., Preissmann M., “Linear recognition of pseudo–split graphs”, Discrete Appl. Math, 52 (1994), 307–312 | DOI | MR | Zbl

[16] Giakoumakis V., Roussel F., Thuillier H., “On $P_4$-tidy graphs”, Discrete Math. and Theor. Comp. Sci, 1 (1997), 17–41 | MR | Zbl

[17] Giakoumakis V., “$P_4$–laden graphs: a new class of brittle graphs”, Inf. Proc. Letters, 60 (1996), 29–36 | DOI | MR | Zbl

[18] Araujo J., Linhares-Sales C., “Grundy number on P4-classes”, Electron. Notes Discrete Math., 35 (2009), 21–27 | DOI | MR | Zbl

[19] Drgas-Burchardt E., “On prime inductive classes of graphs”, European J. Combin., 32:8 (2011), 1317–1328 | DOI | MR | Zbl

[20] Zverovich I. E., Zverovich I. I., The reducing copath method for simple homogeneous sets, Rutcor Research Report, No 19-2001, 2001

[21] 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 | MR | Zbl

[22] Corneil D.G., Perl Y., Stewart L.K., “Cographs: recognition,applications, and algorithms”, Congr. Numer., 43 (1984), 249–258 | MR

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

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

[25] 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 | MR | Zbl

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

[27] 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 | MR | Zbl