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), p. 625-651 / Harvested from Numdam

Résumé

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) ${\rm lab}(x)$ of length $O(\log ^2(n))$ 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.

Détail

Publié le : 2009-01-01

MR 2541134 | Zbl 1176.68139

DOI : https://doi.org/10.1051/ita/2009010
Classification:  68R10,  90C35

Bibliographie

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

[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 1640205 | Zbl 0941.05057

[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 1460735

[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 0961.05062

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

[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 1804711 | Zbl 0972.05023

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

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

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

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

[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 2121050

[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 1480953

[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 2277161

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

[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 2092847 | Zbl 1062.03032

[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 1969938 | Zbl 1006.68542

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

[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 2086610 | Zbl 1068.68104

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

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

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

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

[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 1196733 | Zbl 0798.68059

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