Inductive computations on graphs defined by clique-width expressions

Carrère, Frédérique

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 625-651.

Labelling problems for graphs consist in building distributed data structures, making it possible to check a given graph property or to compute a given function, the arguments of which are vertices. For an inductively computable function $D$, if $G$ is a graph with $n$ vertices and of clique-width at most $k$, where $k$ is fixed, we can associate with each vertex $x$ of $G$ a piece of information (bit sequence) $\mathrm{lab}\left(x\right)$ of length $O\left({log}^2\left(n\right)\right)$ such that we can compute $D$ in constant time, using only the labels of its arguments. The preprocessing can be done in time $O(h.n)$ where $h$ is the height of the syntactic tree of $G$. We perform an inductive computation, without using the tools of monadic second order logic. This enables us to give an explicit labelling scheme and to avoid constants of exponential size.

[1] S. Arnborg, J. Lagergren, D. Seese, Easy problems for tree-decomposable graphs. J. Algor. 12 (1991) 308-340. | MR | Zbl

[2] H. Bodlaender, Treewidth: Algorithmic techniques and results, in Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 1295 (1997) 19-36. | MR | Zbl

[3] R.B. Borie, R.G. Parker, C.A. Tovey, Algorithms on Recursively Constructed Graphs. CRC Handbook of Graph Theory (2003) 1046-1066.

[4] S. Chaudhuri, C.D. Zaroliagis, Optimal parallel shortest paths in small treewidth digraphs, in: Proceedings 3rd Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 979 (1995) 31-45. | MR

[5] D.G. Corneil, M. Habib, J.M. Lanlignel, B.A. Reed, U. Rotics, Polynomial time recognition algorithm of clique-width $\le 3$ graphs, LATIN'00. Lect. Notes Comput. Sci. 1776 (2000) 126-134. | Zbl

[6] B. Courcelle, Clique-width of countable graphs: a compactness property. Discrete Math. 276 (2003) 127-148. | MR | Zbl

[7] B. Courcelle, J.A. Makowsky, U. Rotics, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Appl. Math. 108 (2001) 23-52. | MR | Zbl

[8] B. Courcelle, M. Mosbah, Monadic second-order evaluations of tree-decomposable graphs. Theoret. Comput. Sci. 109 (1993) 49-82. | MR | Zbl

[9] B. Courcelle, S. Olariu, Upper bounds to clique-width of graphs. Discrete Appl. Math. 101 (2000) 77-114. | MR | Zbl

[10] B. Courcelle, A. Twigg, Compact forbidden-set routing, in: STACS'07. Lect. Notes Comput. Sci. 4393 (2007) 37-48. | MR

[11] B. Courcelle, R. Vanicat, Query efficient implementations of graphs of bounded clique-width. Discrete Appl. Math. 131 (2003) 129-150. | MR | Zbl

[12] C. Demetrescu, G.F. Italiano, a new approach to dynamic all pairs shortest paths, in Proceedings of. the 35. th. Annual ACM Symposium on the Theory of Computing (2003) 159-166. | MR

[13] R.G. Downey, M.R. Fellows, Parametrized Complexity. Springer Verlag (1999).

[14] J. Engelfriet, G. Rozenberg, Node replacement graph grammars, in Handbook of Graph Grammars and Computing by Graph Transformation, Foundations, Vol. 1, edited by G. Rozenberg. World Scientific (1997) 1-94. | MR

[15] M.R. Fellows, F.A. Rosamond, U. Rotics, S. Szeider, Clique-width minimization is NP-hard. Proceedings of. the 38. th. Annual ACM Symposium on the Theory of Computing (2006) 354-362. | MR

[16] J. Flum, M. Grohe, Theory of parametrized complexity. Springer Verlag (2006). | MR

[17] M. Frick, M. Grohe, The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130 (2004) 3-31. | MR | Zbl

[18] C. Gavoille, M. Katz, Nir A. Katz, C. Paul, D. Peleg, Approximate distance labeling schemes, ESA'01. Lect. Notes Comput. Sci. 2161 (2001) 476-488. | MR | Zbl

[19] C. Gavoille, C. Paul, Distance labeling scheme and split decomposition. Discrete Math. 273 (2003) 115-130. | MR | Zbl

[20] C. Gavoille, D. Peleg, Compact and localized distributed data structures. J. Distrib. Comput. 16 (2003) 111-120.

[21] C. Gavoille, D. Peleg, S. Pérennes, R. Raz, Distance labeling in graphs. J. Algor. 53 (2004) 85-112. | MR | Zbl

[22] E. Wanke, $k$-NLC graphs and polynomial algorithms. Disc. Appl. Math. 54 (1994) 251-266. | MR | Zbl

[23] F. Gurski, E. Wanke, Vertex disjoint paths on clique-width bounded graphs, LATIN'04. Lect. Notes Comput. Sci. 2978 (2004) 119-128. | MR

[24] D. Harel, R. Tarjan, Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13 (1984) 338-355. | MR | Zbl

[25] P. Hlinený, S. Oum, Finding Branch-Decompositions and Rank-Decompositions. SIAM J. Comput. 38 (2008) 1012-1032. | MR | Zbl

[26] D. Seese, Interpretability and tree automata: A simple way to solve algorithmic problems on graphs closely related to trees, in Tree Automata and Languages, edited by M. Nivat, A. Podelski. North-Holland (1992) 83-114. | MR | Zbl

[27] J.P. Spinrad, Efficient Graph Representations. American Mathematical Society (2003). | MR | Zbl