Identifying path covers in graphs

This paper introduces the problem of identifying vertices of a graph using paths. An identifying path cover of a graph G   is a set PP of paths such that each vertex belongs to a path of PP, and for each pair u, v   of vertices, there is a path of PP which includes exactly one of u, v. This new notion is related to a large number of other identification problems in graphs and hypergraphs. We study the identifying path cover problem under both combinatorial and algorithmic points of view. In particular, we derive the optimal size of an identifying path cover for paths, cycles and hypercubes, and give upper bounds for 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 ⌈2|V(G)|3⌉+5. We then 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 bounded value, the problem is APX-complete.