On graph identification problems and the special case of identifying vertices using paths

Overview & Synopsis

In this paper, we introduce the identifying path cover problem: an \emph{identifying path cover} of a graph $G$ is a set $\mathcal P$ of paths such that each vertex belongs to a path of $\mathcal P$, and for each pair $u,v$ of vertices, there is a path of $\mathcal P$ which includes exactly one of $u,v$. This problem is related to a large variety of identification problems. We investigate the identifying path cover problem in some families of graphs. In particular, we derive the optimal size of an identifying path cover for paths, cycles, hypercubes and topologically irreducible trees and give an upper bound for all trees. We give lower and upper bounds on the minimum size of an identifying path cover for general graphs, and discuss their tightness. In particular, we show that any connected graph $G$ has an identifying path cover of size at most $\left\lceil\frac{2(|V(G)|-1)}{3}\right\rceil$. We also study the computational complexity of the associated optimization problem, in particular we show that when the length of the paths is asked to be of a fixed value, the problem is APX-complete.