×

zbMATH — the first resource for mathematics

Nondeterministic graph searching: from pathwidth to treewidth. (English) Zbl 1172.68046
Summary: We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called \(q\)-branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of \(q\)-branched tree decompositions. The equivalence between nondeterministic graph searching and \(q\)-branched tree decomposition enables us to design an exact (exponential time) algorithm computing \(q\)-branched treewidth for all \(q\geq 0\), which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amini, O., Huc, F., Perennes, S.: On the pathwidth of planar Graphs. SIAM J. Discret. Math. (to appear)
[2] Amir, E.: Efficient approximation for triangulation of minimum treewidth, In: Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference (UAI-2001), San Francisco, CA, pp. 7–15. Morgan Kaufmann (2001)
[3] Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebr. Discret. Methods 8, 277–284 (1987) · Zbl 0611.05022 · doi:10.1137/0608024
[4] Bienstock, D.: Graph searching, path-width, tree-width and related problems (a survey). DIMACS Ser. Discret. Math. Theor. Comput. Sci. 5, 33–49 (1991) · Zbl 0777.05090
[5] Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998) · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4
[6] Coudert, D., Huc, F., Sereni, J.-S.: Pathwidth of outerplanar graphs. J. Graph Theory 55(1), 27–41 (2007) · Zbl 1117.05101 · doi:10.1002/jgt.20218
[7] Dendris, N.D., Kirousis, L.M., Thilikos, D.M.: Fugitive-search games on graphs and related parameters. Theor. Comput. Sci. 172, 233–254 (1997) · Zbl 0903.68052 · doi:10.1016/S0304-3975(96)00177-6
[8] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
[9] Ellis, J.A., Sudborough, I.H., Turner, J.: The vertex separation and search number of a graph. Inf. Comput. 113, 50–79 (1994) · Zbl 0942.68641 · doi:10.1006/inco.1994.1064
[10] Feige, U., Hajiaghayi, M., Lee, J.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 563–572. ACM, New York (2005) · Zbl 1192.68893
[11] Fomin, F.V., Thilikos, D.M.: On self duality of pathwidth in polyhedral graph embeddings. J. Graph Theory 55(1), 42–54 (2007) · Zbl 1117.05028 · doi:10.1002/jgt.20219
[12] Fomin, F.V., Kratsch, D., Todinca, I.: Exact algorithms for treewidth and minimum fill-in. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes in Computer Science, vol. 3142, pp. 568–580. Springer, Berlin (2004) · Zbl 1099.68076
[13] Goldsmith, J., Levy, M., Munhenk, M.: Limited Nondeterminism. SIGACT News, Introduction to Complexity Theory, Column 13, June 1996
[14] Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10, 196–210 (1962) · Zbl 0106.14103 · doi:10.1137/0110015
[15] Kirousis, L.M., Papadimitriou, C.H.: Searching and pebbling. Theor. Comput. Sci. 47, 205–218 (1986) · Zbl 0616.68064 · doi:10.1016/0304-3975(86)90146-5
[16] Makedon, F.S., Papadimitriou, C.H., Sudborough, I.H.: Topological bandwidth. SIAM J. Algebr. Discret. Methods 6, 418–444 (1985) · Zbl 0573.05052 · doi:10.1137/0606044
[17] Makedon, F.S., Sudborough, I.H.: On minimizing width in linear layouts. Discret. Appl. Math. 23, 243–265 (1989) · Zbl 0715.05012 · doi:10.1016/0166-218X(89)90016-4
[18] Mazoit, F., Nisse, N.: Monotonicity property of non-deterministic graph searching. In: Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007) (to appear) · Zbl 1141.68543
[19] Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory Ser. B 52, 153–190 (1991) · Zbl 0764.05069 · doi:10.1016/0095-8956(91)90061-N
[20] Seymour, P., Thomas, R.: Graph searching and a min-max theorem for tree-width. J. Comb. Theory Ser. B 58, 22–33 (1993) · Zbl 0795.05110 · doi:10.1006/jctb.1993.1027
[21] Seymour, P., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14, 217–241 (1994) · Zbl 0799.05057 · doi:10.1007/BF01215352
[22] Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput. 6, 537–546 (1977) · Zbl 0357.68035 · doi:10.1137/0206038
[23] Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization: ”Eureka, you shrink”. Lecture Notes in Computer Science, vol. 2570, pp. 185–207. Springer, Berlin (2003) · Zbl 1024.68529
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.