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

A 2-approximation for the bounded treewidth sparsest cut problem in \(\textsf{FPT}\) Time

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta et al. (ACM STOC, 2013) obtained a 2-approximation with polynomial running time for fixed k, and it remained open the question of whether there exists a c-approximation algorithm for a constant c independent of k, that runs in \(\textsf{FPT}\) time. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in \(\textsf{FPT}\) time, when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in \(\textsf{FPT}\) time.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1

Similar content being viewed by others

Notes

  1. That is, \(f(k)|\mathcal {I}|^{O(1)}\) time for some computable function f.

References

  1. Aprile, M., Drescher, M., Fiorini, S., Huynh, T.: A tight approximation algorithm for the cluster vertex deletion problem. In: Integer Programming and Combinatorial Optimization (IPCO), (2021)

  2. Arora, S., Lee, J., Naor, A.: Euclidean distortion and the sparsest cut. J. Am. Math. Soc. 21(1), 1–21 (2008)

    Article  MathSciNet  Google Scholar 

  3. Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 1–37 (2009)

    Article  MathSciNet  Google Scholar 

  4. Bienstock, D., Munoz, G.: LP formulations for polynomial optimization problems. SIAM J. Opt. 28(2), 1121–1150 (2018)

    Article  MathSciNet  Google Scholar 

  5. Bienstock, D., Ozbay, N.: Tree-width and the Sherali-Adams operator. Discr. Optim. 1(1), 13–21 (2004)

    Article  MathSciNet  Google Scholar 

  6. Bodlaender, H.L.: Nc-algorithms for graphs with small treewidth. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), (1988)

  7. Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge university press, (2004)

  8. Chakrabarti, A., Jaffe, A., Lee, J. R., Vincent, J.: Embeddings of topological graphs: lossy invariants, linearization, and 2-sums. In: IEEE Symposium on Foundations of Computer Science (FOCS), (2008)

  9. Chalermsook, P., Kaul, M., Mnich, M., Spoerhase, J., Uniyal, S., Vaz, D.: Approximating sparsest cut in low-treewidth graphs via combinatorial diameter. CoRR, 2111.06299, (2021)

  10. Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15(2), 94–114 (2006)

    Article  MathSciNet  Google Scholar 

  11. Chekuri, C., Shepherd, F.B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. J. Combin. Theor. Ser. B 103(2), 248–273 (2013)

    Article  MathSciNet  Google Scholar 

  12. Chlamtac, E., Krauthgamer, R., Raghavendra, P.: Approximating sparsest cut in graphs of bounded treewidth. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), (2010)

  13. Cohen-Addad, V., Gupta, V., Klein, P. N., Li, J.: A quasipolynomial \((2+\varepsilon )\)-approximation for planar sparsest cut. In: ACM Symposium on Theory of Computing (STOC), (2021)

  14. Corless, R.M., Gonnet, G.H., Hare, D.E., Jeffrey, D.J., Knuth, D.E.: On the Lambertw function. Adv. Comput. Math. 5(1), 329–359 (1996)

    Article  MathSciNet  Google Scholar 

  15. Davies, S., Kulkarni, J., Rothvoss, T., Tarnawski, J., Zhang, Y.: Scheduling with communication delays via lp hierarchies and clustering ii: Weighted completion times on related machines. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), (2021)

  16. Garg, S.: Quasi-ptas for scheduling with precedences using LP hierarchies. In: International Colloquium on Automata, Languages, and Programming (ICALP), (2018)

  17. Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and \(\ell _1\)-embeddings of graphs. Combinatorica 24(2), 233–269 (2004)

    Article  MathSciNet  Google Scholar 

  18. Gupta, A., Talwar, K., Witmer, D.: Sparsest cut on bounded treewidth graphs: algorithms and hardness results. In: ACM Symposium on Theory of Computing (STOC), (2013)

  19. Khot, S.A., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell _1\). J. ACM 62(1), 1–39 (2015)

    Article  Google Scholar 

  20. Klein, P., Agrawal, A., Ravi, R., Rao, S.: Approximation through multicommodity flow. In: IEEE Symposium on Foundations of Computer Science (FOCS), (1990)

  21. Klein, P., Rao, S., Agrawal, A., Ravi, R.: An approximate max-flow min-cut relation for undirected multicommodity flow, with applications. Combinatorica 15(2), 187–202 (1995)

    Article  MathSciNet  Google Scholar 

  22. Korhonen, T., Lokshtanov, D.: An improved parameterized algorithm for treewidth. In: ACM Symposium on Theory of Computing (STOC), pp. 528–541, (2023)

  23. Lee, J.R., Raghavendra, P.: Coarse differentiation and multi-flows in planar graphs. Discr. Comput. Geom. 43(2), 346–362 (2010)

    Article  MathSciNet  Google Scholar 

  24. Lee, J.R., Sidiropoulos, A.: Pathwidth, trees, and random embeddings. Combinatorica 33(3), 349–374 (2013)

    Article  MathSciNet  Google Scholar 

  25. Magen, A., Moharrami, M.: Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), (2009)

  26. Maiti, B., Rajaraman, R., Stalfa, D., Svitkina, Z., Vijayaraghavan, A.: Scheduling precedence-constrained jobs on related machines with communication delay. In: IEEE Symposium on Foundations of Computer Science (FOCS), (2020)

  27. Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discr. Appl. Math. 27(1–2), 113–123 (1990)

    Article  MathSciNet  Google Scholar 

  28. Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Combin. Theor. Ser. B 31(1), 75–81 (1981)

    Article  MathSciNet  Google Scholar 

  29. Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discr. Math. 3(3), 411–430 (1990)

    Article  MathSciNet  Google Scholar 

  30. Verdugo, V., Verschae, J., Wiese, A.: Breaking symmetries to rescue sum of squares in the case of makespan scheduling. Math. Program. 183, 583–618 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Google Research Zurich, Zurich, Switzerland

    Vincent Cohen-Addad

  2. Department of Computer Science, University of Augsburg, Augsburg, Germany

    Tobias Mömke

  3. Institute of Engineering Sciences, Universidad de O’Higgins, Rancagua, Chile

    Victor Verdugo

Authors
  1. Vincent Cohen-Addad
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tobias Mömke
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Victor Verdugo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Victor Verdugo.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Partially supported by DFG Grant 439522729 (Heisenberg-Grant), DFG Grant 439637648 (Sachbeihilfe), and ANID Grants ACT210005 and FONDECYT 11190789.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cohen-Addad, V., Mömke, T. & Verdugo, V. A 2-approximation for the bounded treewidth sparsest cut problem in \(\textsf{FPT}\) Time. Math. Program. 206, 479–495 (2024). https://doi.org/10.1007/s10107-023-02044-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-023-02044-1

Keywords

Search

Navigation