Abstract
This paper is concerned with a game on graphs called graph searching. The object of this game is to clear all edges of a contaminated graph. Clearing is achieved by moving searchers, a kind of token, along the edges of the graph according to clearing rules. Certain search strategies cause edges that have been cleared to become contaminated again. Megiddo et al. [9] conjectured that every graph can be searched using a minimum number of searchers without this recontamination occurring, that is, without clearing any edge twice. In this paper, this conjecture is proved. This places the graph-searching problem in NP, completing the proof by Megiddo et al. that the graph-searching problem is NP-complete. Furthermore, by eliminating the need to consider recontamination, this result simplifies the analysis of searcher requirements with respect to other properties of graphs.
- 1 ~BIENSTOCK, D., AND SEYMOUR, P. Monotonicity m graph searching. J. Algorithms 12 (1991), ~239-245. Google Scholar
- 2 ~BRElSCH, R. An intuitive approach to speleotopology. Southwestern Cat:ers (A publication of ~the Southwestern Region of the National Speleological Society) VI, 5 (Dec. 1967), 72-78.Google Scholar
- 3 ~ELLIS, J. A., SUDBOROUGH, I. H., AND TURNER, J.S. Graph separation and search number. ~In Proceedings of the Allerton Conference on Communication, Control and Compuung. Coordi- ~nated Sci. Lab., Univ. Illinois, Urbana-Champaign, I11., 1983, pp. 224 233.Google Scholar
- 4 ~GAREY, M. R., AND JOHNSON, D.S. Compttlers and bltractabiliO': A Guide to the Theoo' of ~NP-Completeness. W. H. Freeman and Co., San Francisco, Calif., 1979. Google Scholar
- 5 ~KIROUSIS, L., AND PAPADIMITRIOU, C. Searching and pebbling. Theoret. Comput. Set. 47 ~(1986), 205 218. Google Scholar
- 6 ~MAKEDON, F. Layout problems and their complexity. Ph.D. dissertation. Dept. of Electrical ~Engineering and Computer Science, Northwestern Univ., Chicago, Ill., 1982. Google Scholar
- 7 ~MAKEDON, F., PAPADIMITRIOU, C., AND SUDBOROUGH, I.H. Topological bandwidth. SIAM J. ~Al~: Disc. Meth. 6 (1985), 418-444.Google Scholar
- 8 ~MAKEDON, F., AND SUDBOROUGH, I.H. On minimizing width in linear layouts. Disc. Appl. ~ Math. 23 (1989), 243 265. Google Scholar
- 9 ~MEGiDDO, N., HAKIMI, S. L., GAREY, M. R., JOHNSON, D. S., AND PAPADINiITRIOU, C.H. The ~complexity of searching a graph, J. ACM 35, 1 (Jan. 1988), 18-44. Google Scholar
- 10 ~PARSONS, T.D. Pursuit-evasion in a graph. In Theory and ,4pphcattons of Graphs. Y. Alavi ~ and D. R. Lick, eds. Lecture Notes in Mathematics. Springer-Verlag, New York, 1976, pp. ~ 426-441.Google Scholar
- 11 ~PARSONS, T. D. The search number of a connectcd graph. In Proceedtngs of the 9th ~Southeastern Conference on Combinatodcs, Graph Theoly and Cotnputing. Utilitas Mathemat- ~ica Publishing, Winnipeg, Canada, 1978, pp. 549 554.Google Scholar
Index Terms
- Recontamination does not help to search a graph
Recommendations
Exclusive graph searching vs. pathwidth
In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to ...
Connected graph searching in chordal graphs
Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426-441]: given a ''contaminated'' graph G (e.g., a network containing a ...
Polynomial-time algorithms for Subgraph Isomorphism in small graph classes of perfect graphs
Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as ...
Comments