# Is the isometric path cover problem NP-complete?

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?

• 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$? – Manuel Lafond May 30 '18 at 12:07
• According to Section 4 of this paper, this is an open question. – Yuval Filmus May 30 '18 at 15:03
• @YuvalFilmus That would make a good answer – Draconis May 30 '18 at 19:43