Path Hitting in Acyclic Graphs |
| |
Authors: | Ojas Parekh Danny Segev |
| |
Affiliation: | (1) Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA;(2) Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA |
| |
Abstract: | An instance of the path hitting problem consists of two families of paths,
and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to
and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and
share at least one mutual edge, we say that p
hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of
. In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying
graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that
they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend
the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction
that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover
problem, which may be of independent interest.
An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006.
This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin. |
| |
Keywords: | Approximation algorithms Linear programming Primal-dual Edge cover Edge dominating set Tree augmentation Tree multicut |
本文献已被 SpringerLink 等数据库收录! |
|