zbMATH — the first resource for mathematics

Fugitive-search games on graphs and related parameters. (English) Zbl 0903.68052
Summary: The goal of a fugitive-search game on a graph is to trap a fugitive that hides on the vertices of the graph by systematically placing searchers on the vertices. The fugitive is assumed to have complete knowledge of the graph and of the searchers’ moves, but is restricted to move only along paths whose vertices are not guarded by searchers. The search number of the graph is the least number of searchers necessary to trap the fugitive. Variants of the fugitive-search game have been related to important graph parameters like treewidth and pathwidth. In this paper, we introduce a class of fugitive-search games where the searchers do not see the fugitive and the fugitive can only move just before a searcher is placed on the vertex it occupies. Letting the fugitive’s speed (i.e. the maximum number of edges the fugitive can traverse at a single move) vary, we get different games. We show that if the speed of the fugitive is unbounded then the search number minus 1 is equal to the treewidth of the graph, while if the speed is 1 then the search number minus 1 is equal to a polynomially computable graph parameter which is called width, or alternatively linkage, and is studied in the context of the Constraint Satisfaction and Boolean Satisfiability Problems. We also show that in the above two cases, the search number remains the same even if we consider only search strategies that at every step further restrict the fugitive’s possible resorts (this monotonicity property is usually expressed as: “recontamination does not help”). Moreover, we give an equivalent characterization of the search number for any given fugitive speed in terms of an elimination ordering of the vertices of the graph. Using this characterization, we show that for any graph, if the length of any chordless cycle is bounded by a constant \(s\) \((s\geqslant 3)\), then the treewidth of the graph plus 1 is equal to the search number for fugitive speed \(s-2\).

68P10 Searching and sorting
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Anderson, R.; Mayr, E.; Anderson, R.; Mayr, E., A P-complete problem and approximations to it, (), 4, 17-38, (1987), see also:
[2] Amborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability (a survey), Bit, 25, 2-33, (1985)
[3] Bienstock, D., Graph searching, path-width, tree-width and related problems (a survey), DIMACS ser. discrete math. theoret. comput. sci., 5, 33-49, (1991) · Zbl 0777.05090
[4] Bienstock, D.; Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a forest, J. combin. theory ser. B, 52, 274-283, (1991) · Zbl 0763.05023
[5] Bienstock, D.; Seymour, P.D., Monotonicity in graph searching, J. algorithms, 12, 239-245, (1991) · Zbl 0760.05081
[6] Bodlaender, H.L., Classes of graphs with bounded treewidth, () · Zbl 0684.68047
[7] Bodlaender, H.L., A tourist guide through treewidth, Acta cybernet., 11, 1-21, (1993) · Zbl 0804.68101
[8] Bodlaender, H.L.; Möhring, R.H., The pathwidth and treewidth of cographs, (), 301-309 · Zbl 0773.05091
[9] Bodlaender, H.L.; Thilikos, D.M., Treewidth and small separators for graphs with small chordality, () · Zbl 0895.68113
[10] Breisch, R., An intuitive approach to speleotopology, (), 72-78
[11] Dechter, R., Constraint networks, (), 285-293
[12] Dechter, R., Directional resolution: the Davis-Putnam procedure, (), 29-35, revised in
[13] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artificial intelligence, 38, 353-366, (1989) · Zbl 0665.68084
[14] Ellis, J.A.; Sudborough, I.H.; Turner, J.S., The vertex separation number of a graph, (), 224-233 · Zbl 0942.68641
[15] Franklin, M.; Galil, Z.; Yung, M., Eavesdropping games: a graph-theoretic approach to privacy in distributed systems, (), 670-679
[16] Freuder, E.C., A sufficient condition for backtrack-free search, J. ACM, 29, 24-32, (1982) · Zbl 0477.68063
[17] Freuder, E.C., A sufficient condition for backtrack-bounded search, J. ACM, 32, 755-761, (1985) · Zbl 0633.68096
[18] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[19] Kinnersley, N.G., The vertex separation number of a graph equals its path-width, Inform. process. lett., 42, 345-350, (1992) · Zbl 0764.68121
[20] Kirousis, L.M.; Papadimitriou, C.H., Interval graphs and searching, Discrete math., 55, 181-184, (1985) · Zbl 0566.05056
[21] Kirousis, L.M.; Papadimitriou, C.H., Searching and pebbling, J. theoret. comput. sci., 47, 205-218, (1986) · Zbl 0616.68064
[22] L.M. Kirousis and D.M. Thilikos, The linkage of a graph, SIAM J. Comput., to appear. · Zbl 0851.68035
[23] Kloks, T., Treewidth, () · Zbl 0852.68069
[24] LaPaugh, A.S., Recontamination does not help to search a graph, J. ACM, 40, 224-245, (1993) · Zbl 0768.68048
[25] Mackworth, A., Constraint satisfaction, (), 276-285
[26] Mackworth, A.; Freuder, E., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial intelligence, 25, 65-74, (1985)
[27] Matula, D.W., A MIN-MAX theorem for graphs with application to graph coloring, SIAM rev., 10, 481-482, (1968)
[28] Megiddo, N.; Hakimi, S.L.; Garey, M.R.; Johnson, D.S.; Papadimitriou, C.H., The complexity of searching a graph, J. ACM, 35, 18-44, (1988) · Zbl 0637.68081
[29] Möhring, R.H., Graph problems related to gate matrix layout and PLA folding, (), 17-51 · Zbl 0699.68072
[30] Parsons, T.D., Pursuit-evasion in a graph, (), 426-441 · Zbl 0379.05026
[31] Parsons, T.D., The search number of a connected graph, (), 549-554 · Zbl 0418.05022
[32] Robertson, N.; Seymour, P.D., Graph minors III. planar tree-width, J. combin. theory ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[33] Seymour, P.D.; Thomas, R., Graph searching and a minimax theorem for tree-width, J. combin. theory ser. B, 58, 22-33, (1993) · Zbl 0795.05110
[34] van Leeuwen, J., Graph algorithms, (), 527-631 · Zbl 0900.68258
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.