[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Path Hitting in Acyclic Graphs

  • Conference paper
Algorithms – ESA 2006 (ESA 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4168))

Included in the following conference series:

  • 3106 Accesses

Abstract

An instance of the path hitting problem consists of two families of paths, \({\cal D}\) and \({\cal H}\), in a common undirected graph, where each path in \({\cal H}\) is associated with a non-negative cost. We refer to \({\cal D}\) and \({\cal H}\) as the sets of demand and hitting paths, respectively. When \(p \in {\cal H}\) and \(q \in {\cal D}\) share at least one mutual edge, we say that phits q. The objective is to find a minimum cost subset of \({\cal H}\) whose members collectively hit those of \({\cal D}\).

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.

Due to space limitations, some technical details and proofs are omitted from this extended abstract. We refer the reader to the full version of this paper (currently available online at http://www.math.tau.ac.il/~segevd), in which all missing details are provided.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aráoz, J., Cunningham, W.H., Edmonds, J., Green-Krótki, J.: Reductions to 1-matching polyhedra. Networks 13, 455–473 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  2. Carr, R., Fujito, T., Konjevod, G., Parekh, O.: A \(2 \frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem. Journal of Combinatorial Optimization 5(3), 317–326 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  3. Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. In: 20th CCC, pp. 144–153 (2005)

    Google Scholar 

  4. Edmonds, J., Johnson, E.L.: Matching: A well-solved class of integer linear programs. In: Combinatorial Structures and their Applications, pp. 89–92. Gordon and Breach, New York (1970)

    Google Scholar 

  5. Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol. 2129, pp. 90–101. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  6. Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM 45(4), 634–652 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  7. Frederickson, G.N., JáJá, J.: Approximation algorithm for several graph augmentation problems. SIAM Journal on Computing 10(2), 270–283 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  8. Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discrete Applied Mathematics 118(3), 199–207 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  9. Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM Journal on Computing 25(2), 235–251 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  10. Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  11. Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM Journal on Computing 24(2), 296–317 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  12. Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39–60 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  13. Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9, 256–278 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  14. Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. Journal of Algorithms 14(2), 214–225 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  15. Levin, A., Segev, D.: Partial multicuts in trees. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 320–333. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  16. Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics 13, 383–390 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  17. Murty, K.G., Perin, C.: A 1-matching blossom type algorithm for edge covering problems. Networks 12, 379–391 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  18. Parekh, O.: Edge dominating and hypomatchable sets. In: 13th SODA, pp. 287–291 (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Emory University, USA

    Ojas Parekh

  2. School of Mathematical Sciences, Tel-Aviv University, Israel

    Danny Segev

Authors
  1. Ojas Parekh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Danny Segev
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA and School of Computer Science, Tel-Aviv University, 69978, Tel-Aviv, Israel

    Yossi Azar

  2. Department of Computer Science, University of Leicester, University Road, LE1 7RH, Leicester, UK

    Thomas Erlebach

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Parekh, O., Segev, D. (2006). Path Hitting in Acyclic Graphs. In: Azar, Y., Erlebach, T. (eds) Algorithms – ESA 2006. ESA 2006. Lecture Notes in Computer Science, vol 4168. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11841036_51

Download citation

  • DOI: https://doi.org/10.1007/11841036_51

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-38875-3

  • Online ISBN: 978-3-540-38876-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation