The minimax path location problem is to find a path P in a graph G such that the maximum distance dG(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.
Hao Lin, Cheng He
. On Fixed-Parameter Solvability of the Minimax Path Location Problem[J]. Communications on Applied Mathematics and Computation, 2023
, 5(4)
: 1644
-1654
.
DOI: 10.1007/s42967-022-00238-6
1. Becker, R.I., Lari, I., Scozzari, A., Storchi, G.: The location of median paths on grid graphs. Ann. Oper. Res. 150, 65-78 (2007)
2. Bhattacharya, B., Shi, Q., Tamir, A.: Optimal algorithms for the path/tree-shaped facility location problems in trees. Algorithmica 55, 601-618 (2009)
3. Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, Berlin (2008)
4. Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the NP-Completeness. Freman, New York (1979)
5. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
6. Hakimi, S.L., Schmeichel, E.F., Labbé, M.: On locating path- or tree-shaped facilities on networks. Networks 23, 543-555 (1993)
7. Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems, part I: the p-centers. SIAM J. Appl. Math. 37, 513-538 (1997)
8. Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems, part II: the p-medians. SIAM J. Appl. Math. 37, 539-560 (1997)
9. Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 4th edn. Springer, Berlin (2008)
10. Lazar, A., Tamir, A.: Improved algorithms for some competitive location centroid problems on paths, trees and graphs. Algorithmica 66, 615-640 (2013)
11. Lee, D.T., Wu, Y.F.: Geometric complexity of some location problems. Algorithmica 1, 193-211 (1986)
12. Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Oper. Res. Lett. 1, 194-197 (1982)
13. Minieka, E.: The optimal location of a path or tree in a tree networks. Networks 15, 309-321 (1985)
14. Morgan, C.A., Slater, P.J.: A linear algorithm for a core of a tree. J. Algor. 1, 247-258 (1980)
15. Puerto, J., Ricca, F., Scozzari, A.: Reliability problems in multiple path-shaped facility location on networks. Discrete Optim. 12, 61-72 (2014)
16. Richey, M.B.: Optimal location of a path or tree on a network with cycles. Networks 20, 391-407 (1990)
17. Shang, S., Lin, Y.: Point-line location problems in the plane with min-max objectives. OR Trans. 7(3), 83-91 (2003)
18. Slater, P.J.: Locating central paths in a graph. Transp. Sci. 16(1), 1-18 (1982)
19. Tamir, A., Puerto, J., Mesa, J.A., Rodriguez-Chia, A.M.: Conditional location of path and tree shaped facilities on trees. J. Algor. 56, 50-75 (2005)
20. Zhou, J., Kang, L., Shan, E.: Two paths location of a tree with positive or negative weights. Theor. Comput. Sci. 607, 296-305 (2015)
