License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.519
URN: urn:nbn:de:0030-drops-30402
URL: https://drops.dagstuhl.de/opus/volltexte/2011/3040/
 Go to the corresponding LIPIcs Volume Portal

### New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs

 pdf-format:

### Abstract

By a T-star we mean a complete bipartite graph K_{1,t} for some t <= T. For an undirected graph G, a T-star packing is a collection of node-disjoint T-stars 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 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.

### 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 =	{519--530},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-25-5},
ISSN =	{1868-8969},
year =	{2011},
volume =	{9},
editor =	{Thomas Schwentick and Christoph D{\"u}rr},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3040},
URN =		{urn:nbn:de:0030-drops-30402},
doi =		{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 Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) Issue Date: 2011 Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy