Let ℋ be a family of graphs. An ℋ-packing of a graph G is a set {G1, G2,…,G$$} of disjoint subgraphs of G such that each G$$ is isomorphic to some element of ℋ. An ℋ-packing of a graph G that covers the maximum number of vertices of G is called a maximum ℋ-packing of G. The ℋ-packing problem seeks to find a maximum ℋ-packing of a graph. Let i be a positive integer. An i-star is a complete bipartite graph K$$. This paper investigates the ℋ-packing problem with H being a family of stars. For an arbitrary family 𝒮 of stars, we design a linear-time algorithm for the 𝒮-packing problem in trees. Let t be a positive integer. An ℋ-packing is called a t+-star packing if ℋ consists of i-stars with i ≥ t. We show that the t+-star packing problem for t ≥ 2 is NP-hard in bipartite graphs. As a consequence, the 2+-star packing problem is NP-hard even in bipartite graphs with maximum degree at most 4. Let T and t be two positive integers with T > t. An ℋ-packing is called a T\t-star packing if ℋ={K1,1,K1,2,…,K$$}\{K$$}. For t ≥ 2, we present a t/t+1-approximation algorithm for the T\t-star packing problem that runs in 𝒪(mn1/2) time, where n is the number of vertices and m the number of edges of the input graph. We also design a 1/2-approximation algorithm for the 2+-star packing problem that runs in 𝒪(m) time, where m is the number of edges of the input graph. As a consequence, every connected graph with at least 3 vertices has a 2+-star packing that covers at least half of its vertices.
Keywords: Star, tree, $$-packing, star family packing, $$+-star packing, $$\$$-star packing
@article{RO_2021__55_4_2129_0,
author = {Li, Mengya and Lin, Wensong},
title = {On star family packing of graphs},
journal = {RAIRO. Operations Research},
pages = {2129--2140},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {4},
doi = {10.1051/ro/2021096},
mrnumber = {4282591},
zbl = {1468.05230},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021096/}
}
Li, Mengya; Lin, Wensong. On star family packing of graphs. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2129-2140. doi: 10.1051/ro/2021096
[1] , Personal Communication to Pavol Hell (1996).
[2] and , New exact and approximation algorithms for the star packing problem in undirected graphs. In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. March 10–12, 2011, Dortmund, Germany (2011) 519–530. | MR | Zbl
[3] , and , Oriented star packings. J. Combin. Theory, Ser. B 98 (2008) 558–576. | MR | Zbl | DOI
[4] and , Complexity of approximating bounded variants of optimization problems. Theoret. Comput. Sci. 354 (2006) 320–338. | MR | Zbl | DOI
[5] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979). | MR | Zbl
[6] , and , The -piece packing problem. J. Graph Theory 52 (2006) 267–293. | MR | Zbl | DOI
[7] and , Packing by cliques and by finite families of graphs. Discrete Math. 49 (1984) 45–59. | MR | Zbl | DOI
[8] and , Packing by complete bipartite graphs. SIAM J. Alg. Disc. Meth. 7 (1986) 199–209. | MR | Zbl | DOI
[9] , , and , On restricted two-factors. SIAM J. Discrete Math. 1 (1988) 472–484. | MR | Zbl | DOI
[10] , Optimal packing of induced stars in a graph. Discrete Math. 173 (1997) 97–127. | MR | Zbl | DOI
[11] and , Efficient subgraph packing. J. Combin. Theory Ser. B 59 (1993) 106–121. | MR | Zbl | DOI
[12] , On the star packing problem. In: Vol. 576 of Proc. 1st China-USA International Graph Theory Conference (1989) 411–416. | MR | Zbl
Cité par Sources :
