EUVIMEDEUVIMED entdecken
Crossref

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto

SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 554-575

DOI: 10.1137/24m1720317 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 08.04.2026. Verfasst von Takehiro Ito und 6 weiteren Autor:innen. Die Arbeit nennt 38 Literaturangaben. Gefördert von: Exploratory Research for Advanced Technology, Japan Society for the Promotion of Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of the well-known associahedron. The associahedron is obtained as the graph associahedron of a path. Whether the combinatorial (i.e., graph-theoretic) distance between vertices of the associahedron can be computed in polynomial time is a tantalizing and important open problem, which is identical to the computation of the flip distance between two triangulations of a convex polygon, and the rotation distance between two rooted binary trees. Our result shows that an approach for this open problem is not promising if it is applicable to the generalized problem on graph associahedra. As a corollary of our theorem, we prove that the computation of a combinatorial shortest path between two vertices of a polymatroid base polytope cannot be done in polynomial time unless [Formula: see text]. Since a combinatorial shortest path on the matroid base polytope can be computed in polynomial time, our result reveals an unexpected contrast between matroids and polymatroids.

Förderung

  • Exploratory Research for Advanced Technology
  • Japan Society for the Promotion of Science

Zitieren

APA

Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y., Maezawa, S., Nozaki, Y., & Okamoto, Y. (2026). Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra. SIAM Journal on Discrete Mathematics, 40(2), 554-575. https://doi.org/10.1137/24m1720317

Vancouver

Ito T, Kakimura N, Kamiyama N, Kobayashi Y, Maezawa S, Nozaki Y, et al. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra. SIAM Journal on Discrete Mathematics. 2026;40(2):554-575. doi:10.1137/24m1720317

BibTeX
@article{Ito2026,
  author = {Ito, Takehiro and Kakimura, Naonori and Kamiyama, Naoyuki and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio},
  title = {Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2026},
  volume = {40},
  number = {2},
  pages = {554--575},
  doi = {10.1137/24m1720317}
}
Kostenlos starten →