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

Inapproximability of Shortest Paths on Perfect Matching Polytopes

  • Conference paper
  • First Online:
Integer Programming and Combinatorial Optimization (IPCO 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13904))

  • 815 Accesses

Abstract

We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless \(\textsf{P}=\textsf{NP}\), there is no polynomial-time algorithm that computes a path of constant length between two vertices at distance two of the perfect matching polytope of a bipartite graph. Conditioned on \(\textsf{P}\ne \textsf{NP}\), this disproves a conjecture by Ito, Kakimura, Kamiyama, Kobayashi and Okamoto [SIAM Journal on Discrete Mathematics, 36(2), pp. 1102-1123 (2022)]. Assuming the Exponential Time Hypothesis we prove the stronger result that there exists no polynomial-time algorithm computing a path of length at most \(\left( \frac{1}{4}-o(1)\right) \frac{\log N}{\log \log N}\) between two vertices at distance two of the perfect matching polytope of an N-vertex bipartite graph. These results remain true if the bipartite graph is restricted to be of maximum degree three.

The above has the following interesting implication for the performance of pivot rules for the simplex algorithm on simply-structured combinatorial polytopes: If \(\textsf{P}\ne \textsf{NP}\), then for every simplex pivot rule executable in polynomial time and every constant \(k \in \mathbb {N}\) there exists a linear program on a perfect matching polytope and a starting vertex of the polytope such that the optimal solution can be reached using only two monotone non-degenerate steps from the starting vertex, yet the pivot rule will require at least k non-degenerate steps to reach the optimal solution. This result remains true in the more general setting of pivot rules for so-called circuit-augmentation algorithms.

R. Steiner–Supported by an ETH Postdoctoral Fellowship.

A full version of this article can be found at https://arxiv.org/abs/2210.14608. Proofs of statements marked with \(\star \) are deferred to the full version.

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

Access this chapter

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

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 55.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 69.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We note that the sole prupose of splitting vertices into binary trees is to restrict the maximum degree of the graph, the remainder of the proof is only based on the 4-cycles in the middle of the gadgets.

References

  1. Adler, I., Papadimitriou, C., Rubinstein, A.: On simplex pivoting rules and complexity theory. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 13–24. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07557-0_2

    Chapter  MATH  Google Scholar 

  2. Aichholzer, O., et al.: Flip distances between graph orientations. Algorithmica 83(1), 116–143 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  4. Avis, D., Friedmann, O.: An exponential lower bound for Cunningham’s rule. Math. Program. 161(1–2), 271–305 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  5. Barahona, F., Tardos, É.: Note on Weintraub’s minimum-cost circulation algorithm. SIAM J. Comput. 18(3), 579–583 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  6. Björklund, A., Husfeldt, T., Khanna, S.: Approximating longest directed paths and cycles. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 222–233. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27836-8_21

    Chapter  MATH  Google Scholar 

  7. Bland, R.G.: New finite pivoting rules for the simplex method. Math. Oper. Res. 2(2), 103–107 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bonamy, M., et al.: The perfect matching reconfiguration problem. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26–30, 2019, Aachen, Germany. LIPIcs, vol. 138, pp. 80:1–80:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

    Google Scholar 

  9. Borgwardt, S., Brand, C., Feldmann, A.E., Koutecký, M.: A note on the approximability of deepest-descent circuit steps. Oper. Res. Lett. 49(3), 310–315 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  10. Borgwardt, S., Finhold, E., Hemmecke, R.: On the circuit diameter of dual transportation polyhedra. SIAM J. Discrete Math. 29(1), 113–121 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  11. Borgwardt, S., Viss, C.: A polyhedral model for enumeration and optimization over the set of circuits. Discret. Appl. Math. 308, 68–83 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bousquet, N., Hatanaka, T., Ito, T., Mühlenthaler, M.: Shortest reconfiguration of matchings. In: Sau, I., Thilikos, D.M. (eds.) WG 2019. LNCS, vol. 11789, pp. 162–174. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30786-8_13

    Chapter  Google Scholar 

  13. Chvátal, V.: On certain polytopes associated with graphs. J. Comb. Theory, Ser. B 18(2), 138–154 (1975)

    Google Scholar 

  14. Cioabă, S.M., Royle, G., Tan, Z.K.: On the flip graphs on perfect matchings of complete graphs and signed reversal graphs. Australas. J. Comb. 81, 480–497 (2021)

    MathSciNet  MATH  Google Scholar 

  15. De Loera, J.A., Hemmecke, R., Lee, J.: On augmentation algorithms for linear and integer-linear programming: from Edmonds-Karp to Bland and beyond. SIAM J. Optim. 25(4), 2494–2511 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  16. De Loera, J.A., Kafer, S., Sanità, L.: Pivot rules for circuit-augmentation algorithms in linear optimization. SIAM J. Optim. 32(3), 2156–2179 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  17. Diaconis, P.W., Holmes, S.P.: Matchings and phylogenetic trees. Proc. Natl. Acad. Sci. USA 95(25), 14600–14602 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  18. Diaconis, P.W., Holmes, S.P.: Random walks on trees and matchings. Electron. J. Probab. 7(6), 1–17 (2002)

    MathSciNet  MATH  Google Scholar 

  19. Disser, Y., Friedmann, O., Hopp, A.V.: An exponential lower bound for Zadeh’s pivot rule. CoRR abs/1911.01074 (2019). http://arxiv.org/abs/1911.01074

  20. Disser, Y., Skutella, M.: The simplex algorithm is NP-mighty. ACM Trans. Algorithms 15(1), 5:1–5:19 (2019)

    Google Scholar 

  21. Fearnley, J., Savani, R.: The complexity of the simplex method. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14–17, 2015, pp. 201–208. ACM (2015)

    Google Scholar 

  22. Gabow, H.N., Nie, S.: Finding a long directed cycle. ACM Trans. Algorithms 4(1), 7:1–7:21 (2008)

    Google Scholar 

  23. Gima, T., Ito, T., Kobayashi, Y., Otachi, Y.: Algorithmic meta-theorems for combinatorial reconfiguration revisited. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms, ESA 2022, September 5–9, 2022, Berlin/Potsdam, Germany. LIPIcs, vol. 244, pp. 61:1–61:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

    Google Scholar 

  24. Goldfarb, D., Sit, W.Y.: Worst case behavior of the steepest edge simplex method. Discret. Appl. Math. 1(4), 277–285 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  25. Gupta, M., Kumar, H., Misra, N.: On the complexity of optimal matching reconfiguration. In: Catania, B., Královič, R., Nawrocki, J., Pighizzini, G. (eds.) SOFSEM 2019. LNCS, vol. 11376, pp. 221–233. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-10801-4_18

    Chapter  Google Scholar 

  26. Hansen, T.D., Zwick, U.: An improved version of the random-facet pivoting rule for the simplex algorithm. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14–17, 2015, pp. 209–218. ACM (2015)

    Google Scholar 

  27. van den Heuvel, J.: The complexity of change. In: Blackburn, S.R., Gerke, S., Wildon, M. (eds.) Surveys in Combinatorics 2013, London Mathematical Society Lecture Note Series, vol. 409, pp. 127–160. Cambridge University Press (2013)

    Google Scholar 

  28. Ito, T., et al.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12–14), 1054–1065 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  29. Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y., Okamoto, Y.: Shortest reconfiguration of perfect matchings via alternating cycles. SIAM J. Discret. Math. 36(2), 1102–1123 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  30. Iwata, S.: On matroid intersection adjacency. Discret. Math. 242(1–3), 277–281 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  31. Jeroslow, R.G.: The simplex algorithm with the pivot rule of maximizing criterion improvement. Discret. Math. 4(4), 367–377 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  32. Kafer, S., Pashkovich, K., Sanità, L.: On the circuit diameter of some combinatorial polytopes. SIAM J. Discret. Math. 33(1), 1–25 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  33. Kaminski, M., Medvedev, P., Milanic, M.: Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439, 9–15 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  34. Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), pp. 159–175. Academic Press, New York (1972)

    Google Scholar 

  35. Monroy, R.F., Flores-Peñaloza, D., Huemer, C., Hurtado, F., Wood, D.R., Urrutia, J.: On the chromatic number of some flip graphs. Discret. Math. Theor. Comput. Sci. 11(2), 47–56 (2009)

    MathSciNet  MATH  Google Scholar 

  36. Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  37. Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383–412 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  38. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24. Springer (2003)

    Google Scholar 

  39. Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the International Congress of Mathematicians (ICM 2018), pp. 3447–3487. World Scientific (2018)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université Libre de Bruxelles (ULB), Brussels, Belgium

    Jean Cardinal

  2. ETH Zurich, Zürich, Switzerland

    Raphael Steiner

Authors
  1. Jean Cardinal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Raphael Steiner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Raphael Steiner .

Editor information

Editors and Affiliations

  1. University of Wisconsin-Madison, Madison, WI, USA

    Alberto Del Pia

  2. Otto-von-Guericke-Universität, Magdeburg, Sachsen-Anhalt, Germany

    Volker Kaibel

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Cardinal, J., Steiner, R. (2023). Inapproximability of Shortest Paths on Perfect Matching Polytopes. In: Del Pia, A., Kaibel, V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2023. Lecture Notes in Computer Science, vol 13904. Springer, Cham. https://doi.org/10.1007/978-3-031-32726-1_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-32726-1_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-32725-4

  • Online ISBN: 978-3-031-32726-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation