Recontamination does not help to search a graph

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.

REFERENCES

• 1: D. Bienstock , Paul Seymour, Monotonicity in graph searching, Journal of Algorithms, v.12 n.2, p.239-245, June 1991 [doi>10.1016/0196-6774(91)90003-H]
• 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.
• 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.
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: M Kirousis , C H Papadimitriou, Searching and pebbling, Theoretical Computer Science, v.47 n.2, p.205-218, Nov. 1986
• 6: Fillia Makedon, Layout problems and their complexity, 1982
• 7: ~MAKEDON, F., PAPADIMITRIOU, C., AND SUDBOROUGH, I.H. Topological bandwidth. SIAM J. ~Al~: Disc. Meth. 6 (1985), 418-444.
• 8: Fillia Makedon , Ivan Hal Sudborough, On minimizing width in linear layouts, Discrete Applied Mathematics, v.23 n.3, p.243-265, June 1989 [doi>10.1016/0166-218X(89)90016-4 ]
• 9: N. Megiddo , S. L. Hakimi , M. R. Garey , D. S. Johnson , C. H. Papadimitriou, The complexity of searching a graph, Journal of the ACM (JACM), v.35 n.1, p.18-44, Jan. 1988 [doi>10.1145/42267.42268]
• 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.
• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
NP-completeness, graph searching, pursuit and evasion