patternMinor
Is the isometric path cover problem NP-complete?
Viewed 0 times
problempaththeisometriccompletecover
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#92487, answer score: 3
Revisions (0)
No revisions yet.