Document Open Access Logo

On Extended Formulations For Parameterized Steiner Trees

Authors Andreas Emil Feldmann , Ashutosh Rai

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.18.pdf
  • Filesize: 0.76 MB
  • 16 pages

Document Identifiers

Author Details

Andreas Emil Feldmann
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic
Ashutosh Rai
  • Department of Mathematics, IIT Delhi, India

Funding

  • Feldmann, Andreas Emil: Supported by the Czech Science Foundation GAČR (grant #19-27871X), and by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004).
  • Rai, Ashutosh: Major part of the work was done when the author was at Charles University, funded by Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004).

Acknowledgements

We would like to thank Petr Kolman and Hans Raj Tiwary for helpful discussions.

Cite AsGet BibTex

Andreas Emil Feldmann and Ashutosh Rai. On Extended Formulations For Parameterized Steiner Trees. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.18

Abstract

We present a novel linear program (LP) for the Steiner Tree problem, where a set of terminal vertices needs to be connected by a minimum weight tree in a graph G = (V,E) with non-negative edge weights. This well-studied problem is NP-hard and therefore does not have a compact extended formulation (describing the convex hull of all Steiner trees) of polynomial size, unless P=NP. On the other hand, Steiner Tree is fixed-parameter tractable (FPT) when parameterized by the number k of terminals, and can be solved in O(3^k|V|+2^k|V|²) time via the Dreyfus-Wagner algorithm. A natural question thus is whether the Steiner Tree problem admits an extended formulation of comparable size. We first answer this in the negative by proving a lower bound on the extension complexity of the Steiner Tree polytope, which, for some constant c > 0, implies that no extended formulation of size f(k)2^{cn} exists for any function f. However, we are able to circumvent this lower bound due to the fact that the edge weights are non-negative: we prove that Steiner Tree admits an integral LP with O(3^k|E|) variables and constraints. The size of our LP matches the runtime of the Dreyfus-Wagner algorithm, and our poof gives a polyhedral perspective on this classic algorithm. Our proof is simple, and additionally improves on a previous result by Siebert et al. [2018], who gave an integral LP of size O((2k/e)^k)|V|^{O(1)}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Steiner trees
  • integral linear program
  • extension complexity
  • fixed-parameter tractability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Egon Balas. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM Journal on Algebraic Discrete Methods, 6(3):466-486, 1985. Google Scholar
  2. Egon Balas. Disjunctive programming: Properties of the convex hull of feasible points. Discrete Applied Mathematics, 89(1-3):3-44, 1998. Google Scholar
  3. Francisco Barahona. On cuts and matchings in planar graphs. Mathematical Programming, 60(1):53-68, June 1993. URL: https://doi.org/10.1007/BF01580600.
  4. Austin Buchanan. Extended formulations for vertex cover. Operations Research Letters, 44(3):374-378, 2016. Google Scholar
  5. Austin Loyd Buchanan. Parameterized Approaches for Large-Scale Optimization Problems. PhD thesis, 2015. Google Scholar
  6. J. Byrka, F. Grandoni, T. Rothvoß, and Laura Sanità. An improved LP-based approximation for Steiner tree. In Proc. 42nd STOC, pages 583-592, 2010. URL: https://doi.org/10.1145/1806689.1806769.
  7. Deeparnab Chakrabarty, Jochen Könemann, and David Pritchard. Hypergraphic lp relaxations for steiner trees. In International Conference on Integer Programming and Combinatorial Optimization, pages 383-396. Springer, 2010. Google Scholar
  8. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. Google Scholar
  9. Jun-Dong Cho. Steiner Tree Problems in VLSI Layout Designs, pages 101-173. Springer US, Boston, MA, 2001. Google Scholar
  10. Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Extended formulations in combinatorial optimization. Annals of Operations Research, 204(1):97-143, 2013. Google Scholar
  11. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  12. S. E. Dreyfus and R. A. Wagner. The steiner problem in graphs. Networks, 1(3):195-207, 1971. Google Scholar
  13. Bernhard Fuchs, Walter Kern, D Molle, Stefan Richter, Peter Rossmanith, and Xinhui Wang. Dynamic programming for minimum steiner trees. Theory of Computing Systems, 41(3):493-500, 2007. Google Scholar
  14. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. Google Scholar
  15. Michel X Goemans and Young-Soo Myung. A catalog of steiner tree formulations. Networks, 23(1):19-28, 1993. Google Scholar
  16. F.K. Hwang, D.S. Richards, and P. Winter. The Steiner Tree Problem. ISSN. Elsevier Science, 1992. Google Scholar
  17. A.B. Kahng and G. Robins. On Optimal Interconnections for VLSI. The Springer International in Engineering and Computer Science. Springer US, 2013. Google Scholar
  18. V Kaibel. Extended formulations in combinatorial optimization. Optima 85, page 14. URL: http://www.mathopt.org/Optima-Issues/optima85.pdf.
  19. R. M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  20. Petr Kolman, Martin Koutecky, and Hans Raj Tiwary. Extension complexity, mso logic, and treewidth. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016. Google Scholar
  21. Bernhard Korte and Jens Vygen. Combinatorial optimization, volume 2. Springer. Google Scholar
  22. B.H. Korte. Paths, flows, and VLSI-layout. Algorithms and combinatorics. Springer-Verlag, 1990. Google Scholar
  23. R. Kipp Martin. Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett., 10(3):119-128, 1991. URL: https://doi.org/10.1016/0167-6377(91)90028-N.
  24. R. Kipp Martin, Ronald L. Rardin, and Brian A. Campbell. Polyhedral characterization of discrete dynamic programming. Operations Research, 38(1):127-138, 1990. URL: http://www.jstor.org/stable/171304.
  25. Jesper Nederlof. Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica, 65(4):868-884, 2013. Google Scholar
  26. Thomas Rothvoss. The matching polytope has exponential extension complexity. J. ACM, 64(6):41:1-41:19, 2017. Google Scholar
  27. Matias Siebert, Shabbir Ahmed, and George Nemhauser. A linear programming based approach to the steiner tree problem with a fixed number of terminals. Networks, n/a(n/a). Google Scholar
  28. François Vanderbeck and Laurence A. Wolsey. Reformulation and Decomposition of Integer Programs, pages 431-502. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact