×

Complexity of searching an immobile hider in a graph. (English) Zbl 0890.68105

Summary: We study the computational complexity of certain search-hide games on a graph. There are two players, called searcher and hider. The hider is immobile and hides in one of the nodes of the graph. The searcher selects a starting node and a search path of length at most \(k\). His objective is to detect the hider, which he does with certainty if he visits the node chosen for hiding. Finding the optimal randomized strategies in this zero-sum game defines a fractional path covering problem and its dual, a fractional packing problem. If the length \(k\) of the search path is arbitrary, then the problem is NP-hard. The problem remains NP-hard if the searcher may freely revisit nodes that he has seen before. In that case, the searcher selects a connected subgraph of \(k\) nodes rather than a path of \(k\) nodes. If \(k\) is logarithmic in the number of nodes of the graph, then the problem can be solved in polynomial time. This is shown using a recent technique called color-coding due to Alon, Yuster and Zwick. The same results hold for edges instead of nodes, that is, if the hider hides in an edge and the searcher searches \(k\) edges on a path or on a connected subgraph.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
91A43 Games involving graphs
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahlswede, R.; Wegener, I., Search Problems (1987), Wiley: Wiley New York
[2] Alon, N.; Yuster, R.; Zwick, U., Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs, (Proc. 26th ACM Symp. Theory of Computing (1994)), 326-335 · Zbl 1344.68092
[3] R. Avenhaus, B. von Stengel and S. Zamir, Inspection games, in: R.J. Aumann and S. Hart, eds., Handbook of Game Theory, Vol. 3 (North-Holland, Amsterdam, to appear).; R. Avenhaus, B. von Stengel and S. Zamir, Inspection games, in: R.J. Aumann and S. Hart, eds., Handbook of Game Theory, Vol. 3 (North-Holland, Amsterdam, to appear). · Zbl 0909.90289
[4] Benkoski, S.; Monticino, M. G.; Weisinger, J. R., A survey of the search theory literature, Naval Res. Logist., 38, 469-494 (1991) · Zbl 0731.90043
[5] Bienstock, D.; Seymour, P., Monotonicity in graph searching, J. Algorithms, 12, 230-245 (1991) · Zbl 0760.05081
[6] Cao, B., Search-hide games on trees, Eur. J. Oper. Res., 80, 175-183 (1993) · Zbl 0928.91009
[7] Cao, B.; von Stengel, B., Search-hide games on graphs, (Technical Report S-9303 (1993), University of the Federal Armed Forces Munich: University of the Federal Armed Forces Munich Germany)
[8] Chung, F. R.K.; Cohen, J. E.; Graham, R. L., Pursuit-evasion games on graphs, J. Graph Theory, 12, 159-167 (1988) · Zbl 0664.90097
[9] Fischetti, M.; Hamacher, H. W.; Jørnsten, K.; Maiffioli, F., Weighted \(k\)-cardinality trees: complexity and polyhedral structure, Networks, 24, 11-21 (1994) · Zbl 0809.90124
[10] Franklin, M.; Galil, Z.; Yung, M., Eavesdropping games: a graph-theoretic approach to privacy in distributed systems, (Proc. 34th IEEE Symp. Foundations of Computer Science (1993)), 670-679
[11] Gal, S., Search Games (1980), Academic Press: Academic Press New York · Zbl 0439.90102
[12] Gal, S., Continuous search games, (Chudnovsky, D. V.; Chudnovsky, G. V., Search Theory-Some Recent Developments (1989), Dekker: Dekker New York), 33-53
[13] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer: Springer Berlin · Zbl 0634.05001
[14] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-103 · Zbl 0366.68041
[15] (Lawler, E. L.; etal., The Traveling Salesman Problem (1985), Wiley: Wiley Chichester) · Zbl 0563.90075
[16] Lössner, U.; Wegener, I., Discrete sequential search with positive switch cost, Math. Oper. Res., 7, 426-440 (1982) · Zbl 0498.90047
[17] Lovász, L.; Plummer, M. D., Matching Theory, (Ann. Discrete Math., Vol. 29 (1986), North-Holland: North-Holland Amsterdam) · Zbl 0618.05001
[18] Megiddo, N., The complexity of searching a graph, J. ACM, 35, 18-44 (1988) · Zbl 0637.68081
[19] Monien, B., How to find long paths efficiently, (Ausiello, G.; Lucertini, M., Analysis and Design of Algorithms for Combinatorial Problems. Analysis and Design of Algorithms for Combinatorial Problems, Ann. Discrete Math., Vol. 25 (1985), North-Holland: North-Holland Amsterdam), 239-254 · Zbl 0603.68069
[20] Nemhauser, G. L.; Trotter, L. R., Properties of vertex packing and independence system polyhedra, Math. Programming, 6, 48-61 (1974) · Zbl 0281.90072
[21] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052
[22] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading · Zbl 0557.68033
[23] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley: Wiley Chichester · Zbl 0665.90063
[24] Trummel, K. E.; Weisinger, J. R., The complexity of the optimal searcher path problem, Oper. Res., 34, 324-327 (1986) · Zbl 0615.90072
[25] Wegener, I., Optimal search with positive switch cost is NP-hard, Inform. Process. Lett., 21, 49-52 (1985) · Zbl 0577.90041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.