New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs
Maxim A. Babenko, Alexey Gusakov · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2011
By a T-star we mean a complete bipartite graph K_{1,t} for some t = 2. Hell and Kirkpatrick devised an ad-hoc augmenting algorithm that finds a T-star packing covering the maximum number of nodes. The latter algorithm also yields a min-max formula. We show that T-star packings are reducible to network flows, hence the above problem is solvable in $O(m sqrt(n))$ time (hereinafter n denotes the number of nodes in G, and m --- the number of edges). For the edge-weighted case (in which weights may be assumed positive) finding a maximum $T$-packing is NP-hard. A novel 9/4 T/(T + 1)-factor approximation algorithm is presented. For non-negative node weights the problem reduces to a special case of a max-cost flow. We develop a divide-and-conquer approach that solves it in O(m sqrt(n) log(n)) time. The node-weighted problem with arbitrary weights is more difficult. We prove that it is NP-hard for T >= 3 and is solvable in strongly-polynomial time for T = 2.