Isometric path (like geodesic) is yet another name for shortest path. An isometric path cover is a set $S$ of isometric paths such that every vertex $v ∈ V$ belongs to at least one isometric path of $S$. The isometric path cover problem is to find a minimum cardinality isometric path cover of $G$. Is the isometric path cover problem NP-complete for general graphs?

  • $\begingroup$ So you mean that the path cover can only contain a path $P$ if there exist $x$ and $y$ such that $P$ is a shortest path from $x$ to $y$? $\endgroup$ – Manuel Lafond May 30 '18 at 12:07
  • 1
    $\begingroup$ According to Section 4 of this paper, this is an open question. $\endgroup$ – Yuval Filmus May 30 '18 at 15:03
  • $\begingroup$ @YuvalFilmus That would make a good answer $\endgroup$ – Draconis May 30 '18 at 19:43

This question is mentioned in a recent (2017) paper, Strong geodetic problem in networks: computational complexity and solution for Apollonian networks by Paul Manuel, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj, and Elizabeth Thomas. On page 8, they state:

To our knowledge, the complexity status of the isometric path problem is not known.


The isometric problem is important because of the following reasons: The path cover problem is NP-complete. The induced path-cover problem is NP-compete. The status of the isometric path cover problem is unknown.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.