Geodesic
Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs of bounded treewidth
Trudy Instituta matematiki, Tome 23 (2015) no. 1, pp. 98-114.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. We present an algorithm to solve this problem for graphs that are given together with a tree decomposition $(\{X_i|i\in I\},T)$ in time $O(2^kmk),$ where $m=|I|$ and $k$ denotes the width of the tree decomposition. If $\omega_V(u)=0$ for all $u\in V(G),$ and $\omega_E(e)=1$ for all $e\in E(G)$ then an independent $\{K_1,K_2\}$-packing of maximum weight give an optimal solution the induced matching problem on graph $G.$ Our result improves the $O(4^km)$ algorithm of Moser and Sikdar for solution of the induced matching problem. 
@article{TIMB_2015_23_1_a7,
     author = {V. V. Lepin},
     title = {Solving the problem of finding an independent  $\{K_1,K_2\}$-packing of maximum weight on graphs of bounded treewidth},
     journal = {Trudy Instituta matematiki},
     pages = {98--114},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2015_23_1_a7/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - Solving the problem of finding an independent  $\{K_1,K_2\}$-packing of maximum weight on graphs of bounded treewidth
JO  - Trudy Instituta matematiki
PY  - 2015
SP  - 98
EP  - 114
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2015_23_1_a7/
LA  - ru
ID  - TIMB_2015_23_1_a7
ER  - 
%0 Journal Article
%A V. V. Lepin
%T Solving the problem of finding an independent  $\{K_1,K_2\}$-packing of maximum weight on graphs of bounded treewidth
%J Trudy Instituta matematiki
%D 2015
%P 98-114
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2015_23_1_a7/
%G ru
%F TIMB_2015_23_1_a7
V. V. Lepin. Solving the problem of finding an independent  $\{K_1,K_2\}$-packing of maximum weight on graphs of bounded treewidth. Trudy Instituta matematiki, Tome 23 (2015) no. 1, pp. 98-114. http://geodesic.mathdoc.fr/item/TIMB_2015_23_1_a7/

[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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[18] Moser H., Sikdar S., “The parameterized complexity of induced matching problem”, Discr. Appl. Math., 157 (2009), 715–727 | DOI | MR | Zbl

[19] Robertson N., Seymour D., “Graph Minor. II: Algorithmic aspects of tree width”, J. Algorithms, 7 (1986), 309–322 | DOI | MR | Zbl

[20] Bodlaender H. L., “A tourist guide through treewidth”, Acta Cybernetica, 11:1–2 (1993), 1–22 | MR

[21] Bodlaender H. L., “Treewidth: Structure and algorithms”, LNCS, 4474, 2007, 11–25 | MR | Zbl

[22] Bodlaender H. L., Koster A. M. C. A., “Combinatorial Optimization on Graphs of Bounded Treewidth”, The Computer Journal, 51:3 (2008), 255–269 | DOI | MR

[23] Arnborg S., Corneil D. G., Proskurowski A., “Complexity of finding embeddings in a k-tree”, SIAM J. Algebraic Discrete Meth., 8:2 (1987), 277–284 | DOI | MR | Zbl

[24] Bodlaender H. L., “A linear-time algorithm for finding tree decompositions of small treewidth”, SIAM J. Comput., 25 (1996), 1305–1317 | DOI | MR | Zbl

[25] Perkovic' L., Reed B., “An Improved Algorithm for Finding Tree Decompositions of Small Width”, Lecture Notes In Computer Science, 1665, 1999, 148–154 | DOI | MR | Zbl

[26] Bodlaender H. L., Kloks T., “Efficient and constructive algorithms for the pathwidth and treewidth of graphs”, J. Algorithms, 21 (1996), 358–402 | DOI | MR | Zbl

[27] Kloks T., Treewidth: Computations and Approximations, Lecture Notes in Computer Science, 842, 1994, 218 pp. | DOI | MR | Zbl

[28] Bodlaender H. L., Bonsma P., Lokshtanov D., “The Fine Details of Fast Dynamic Programming over Tree Decompositions”, LNCS, 8246, 2013, 41–53 | MR | Zbl

[29] Arnborg S., Proskurowski A., “Linear time algorithms for NP-hard problems restricted to partial k-trees”, Discrete Appl. Math., 23:1 (1989), 11–24 | DOI | MR | Zbl

[30] Bern M. W., Lawler E. L., Wong A. L., “Linear time computation of optimal subgraphs of decomposable graphs”, J. Algorithms, 8 (1987), 216–235 | DOI | MR | Zbl

[31] Bodlaender H. L., “Treewidth: Algorithmic techniques and results”, Proc. 22nd Internat. Symposium on Mathematical Foundations of Computer Science (1997), 19–36 | MR | Zbl

[32] Niedermeier R., Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006 | MR | Zbl

[33] Downey R., Fellows M., Parameterized complexity, Springer, 1999 | MR | Zbl

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