On star family packing of graphs
Mengya Li, Wensong Lin · RAIRO - Operations Research · 2021
Let ℋ be a family of graphs. An ℋ-packing of a graph G is a set {G1, G2,…,Gk} of disjoint subgraphs of G such that each Gj 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 K1,i. 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,…,K1,T}\{K1,t}. 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.