DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2011.519

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

Authors: Maxim Babenko and Alexey Gusakov

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

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.

Cite as

Maxim Babenko and Alexey Gusakov. 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 519-530, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{babenko_et_al:LIPIcs.STACS.2011.519,
  author =	{Babenko, Maxim and Gusakov, Alexey},
  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 =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.519},
  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}
}

Search Results

Documents authored by Gusakov, Alexey

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

Abstract

Cite as

Thanks for your feedback!

Could not send message