Babenko, Maxim ;
Gusakov, Alexey
New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs
Abstract
By a Tstar we mean a complete bipartite graph K_{1,t} for some t <= T. For an undirected graph G, a Tstar packing is a collection of nodedisjoint Tstars in G.
For example, we get ordinary matchings for $T = 1$ and packings of paths of length 1 and 2 for $T = 2$. Hereinafter we assume that T >= 2.
Hell and Kirkpatrick devised an adhoc augmenting algorithm that finds a Tstar packing covering the maximum number of nodes. The latter algorithm also yields a minmax formula.
We show that Tstar 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 edgeweighted case (in which weights may be assumed positive) finding a maximum $T$packing is NPhard. A novel 9/4 T/(T + 1)factor approximation algorithm is presented.
For nonnegative node weights the problem reduces to a special case of a maxcost flow. We develop a divideandconquer approach that solves it in O(m sqrt(n) log(n)) time. The nodeweighted problem with arbitrary weights is more difficult. We prove that it is NPhard for T >= 3 and is solvable in stronglypolynomial time for T = 2.
BibTeX  Entry
@InProceedings{babenko_et_al:LIPIcs:2011:3040,
author = {Maxim Babenko and Alexey Gusakov},
title = {{New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {519530},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3040},
URN = {urn:nbn:de:0030drops30402},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.519},
annote = {Keywords: graph algorithms, approximation algorithms, generalized matchings, flows, weighted packings}
}
Keywords: 

graph algorithms, approximation algorithms, generalized matchings, flows, weighted packings 
Seminar: 

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Issue date: 

2011 
Date of publication: 

11.03.2011 