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$
$\endgroup$
3
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
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.
answered May 31 '18 at 13:44
$\begingroup$
$\endgroup$
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.
