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 ∈ 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) \le k$. If the answer is affirmative, then graph G is called k-patheccentric. 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.

Key words: Discrete location, Path location, Fixed-parameter solvability, Graph characterization, Polynomial-time algorithm