On Fixed-Parameter Solvability of the Minimax Path Location Problem

Abstract

The minimax path location problem is to find a path P in a graph G such that the maximum distance $d_G(v,P)$ from every vertex $v\in V(G)$ to the path P is minimized. It is a well-known NP-hard problem in network optimization. This paper studies the fixed-parameter solvability, that is, for a given graph G and an integer k, to decide whether there exists a path P in G such that $\mathop{\max}\limits_{v\in V(G)}d_G(v,P)\leqslant k$. If the answer is affirmative, then graph G is called k-path-eccentric. We show that this decision problem is NP-complete even for $k=1$. On the other hand, we characterize the family of 1-path-eccentric graphs, including the traceable, interval, split, permutation graphs and others. Furthermore, some polynomially solvable special graphs are discussed.