Abstract
We introduce the notion of z-topological orderings for digraphs. We prove that given a digraph G on n vertices admitting a z-topological ordering, together with such an ordering, one may count the number of subgraphs of G that at the same time satisfy a monadic second order formula ϕ and are the union of k directed paths, in time f(ϕ,k,z)·n O(k·z). Our result implies the polynomial time solvability of many natural counting problems on digraphs admitting z-topological orderings for constant values of z and k. Concerning the relationship between z-topological orderability and other digraph width measures, we observe that any digraph of directed path-width d has a z-topological ordering for z ≤ 2d + 1. On the other hand, there are digraphs on n vertices admitting a z-topological order for z = 2, but whose directed path-width is Θ(logn). Since graphs of bounded directed path-width can have both arbitrarily large undirected tree-width and arbitrarily large clique width, our result provides for the first time a suitable way of partially transposing metatheorems developed in the context of the monadic second order logic of graphs of constant undirected tree-width and constant clique width to the realm of digraph width measures that are closed under taking subgraphs and whose constant levels incorporate families of graphs of arbitrarily large undirected tree-width and arbitrarily large clique width.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Ajtai, M., Fagin, R., Stockmeyer, L.J.: The closure of monadic NP. J. Comput. Syst. Sci. 60(3), 660–716 (2000)
Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308–340 (1991)
Artin, E.: The theory of braids. Annals of Mathematics 48(1), 101–126 (1947)
Barát, J.: Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics 22(2), 161–172 (2006)
Bauderon, M., Courcelle, B.: Graph expressions and graph rewritings. Mathematical Systems Theory 20(2-3), 83–127 (1987)
Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S., Obdrzálek, J.: The DAG-width of directed graphs. J. Comb. Theory, Ser. B 102(4), 900–923 (2012)
Berwanger, D., Grädel, E.: Entanglement - A measure for the complexity of directed graphs with applications to logic and games. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol. 3452, pp. 209–223. Springer, Heidelberg (2005)
Berwanger, D., Grädel, E., Kaiser, L., Rabinovich, R.: Entanglement and the complexity of directed graphs. Theor. Comput. Sci. 463, 2–25 (2012)
Borie, R.B., Parker, R.G., Tovey, C.A.: Deterministic decomposition of recursive graph classes. SIAM J. Discrete Math. 4(4), 481–501 (1991)
Bozapalidis, S., Kalampakas, A.: Recognizability of graph and pattern languages. Acta Inf. 42(8-9), 553–581 (2006)
Brandenburg, F.-J., Skodinis, K.: Finite graph automata for linear and boundary graph languages. Theoretical Computer Science 332(1-3), 199–232 (2005)
Courcelle, B.: Graph expressions and graph rewritings. Math. Syst. Theory 20, 83–127 (1987)
Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, pp. 194–242 (1990)
Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, vol. 138. Cambridge University Press (2012)
Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Th. of Comp. Syst. 33(2), 125–150 (2000)
Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics 108(1-2), 23–52 (2001)
de Oliveira Oliveira, M.: Hasse diagram generators and Petri nets. Fundam. Inform. 105(3), 263–289 (2010)
de Oliveira Oliveira, M.: Canonizable partial order generators. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 445–457. Springer, Heidelberg (2012)
de Oliveira Oliveira, M.: Subgraphs satisfying MSO properties on z-topologically orderable digraphs. Preprint (full version of this paper) arXiv:1303.4443 (2013)
Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Complexity Theory: Current Research, pp. 191–225 (1992)
Eggan, L.C.: Transition graphs and the star height of regular events. Michigan Mathematical Journal 10(4), 385–397 (1963)
Engelfriet, J., Vereijken, J.J.: Context-free graph grammars and concatenation of graphs. Acta Informatica 34(10), 773–803 (1997)
Evans, W., Hunter, P., Safari, M.: D-width and cops and robbers. Manuscript (2007)
Ganian, R., Hliněný, P., Kneis, J., Langer, A., Obdržálek, J., Rossmanith, P.: On digraph width measures in parameterized algorithmics. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 185–197. Springer, Heidelberg (2009)
Ganian, R., Hliněný, P., Kneis, J., Meister, D., Obdržálek, J., Rossmanith, P., Sikdar, S.: Are there any good digraph width measures? In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 135–146. Springer, Heidelberg (2010)
Ganian, R., Hlinený, P., Langer, A., Obdrzálek, J., Rossmanith, P., Sikdar, S.: Lower bounds on the complexity of MSO1 model-checking. In: STACS 2012, vol. 14, pp. 326–337 (2012)
Giammarresi, D., Restivo, A.: Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence 6(2-3), 241–256 (1992)
Giammarresi, D., Restivo, A.: Two-dimensional finite state recognizability. Fundam. Inform. 25(3), 399–422 (1996)
Gruber, H.: On the d-width of directed graphs. Manuscript (2007)
Gruber, H.: Digraph complexity measures and applications in formal language theory. Discrete Math. & Theor. Computer Science 14(2), 189–204 (2012)
Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 39–50. Springer, Heidelberg (2008)
Hunter, P., Kreutzer, S.: Digraph measures: Kelly decompositions, games, and orderings. Theor. Comput. Sci. 399(3), 206–219 (2008)
Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory, Ser. B 82(1), 138–154 (2001)
Kreutzer, S.: On the parameterized intractability of monadic second-order logic. Logical Methods in Computer Science 8(1) (2012)
Kreutzer, S., Tazari, S.: Lower bounds for the complexity of monadic second-order logic. In: LICS, pp. 189–198 (2010)
Lampis, M., Kaouri, G., Mitsou, V.: On the algorithmic effectiveness of digraph decompositions and complexity measures. Discrete Optimization 8(1), 129–138 (2011)
Matz, O., Thomas, W.: The monadic quantifier alternation hierarchy over graphs is infinite. In: LICS, pp. 236–244 (1997)
Post, E.L.: A variant of a recursively unsolvable problem. Bulletion of the American Mathematical Society 52, 264–268 (1946)
Reed, B.A.: Introducing directed tree width. Electronic Notes in Discrete Mathematics 3, 222–229 (1999)
Safari, M.A.: D-width: A more natural measure for directed tree width. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 745–756. Springer, Heidelberg (2005)
Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 482–493. Springer, Heidelberg (2003)
Tamaki, H.: A polynomial time algorithm for bounded directed pathwidth. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 331–342. Springer, Heidelberg (2011)
Thomas, W.: Finite-state recognizability of graph properties. Theorie des Automates et Applications 172, 147–159 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
de Oliveira Oliveira, M. (2013). Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs. In: Gutin, G., Szeider, S. (eds) Parameterized and Exact Computation. IPEC 2013. Lecture Notes in Computer Science, vol 8246. Springer, Cham. https://doi.org/10.1007/978-3-319-03898-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-03898-8_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03897-1
Online ISBN: 978-3-319-03898-8
eBook Packages: Computer ScienceComputer Science (R0)