Research activities of Bruno Courcelle
LaBRI, (CNRS Laboratory umr 5800)
Bordeaux 1 University,
Research Group : Logique, Automates, Algorithmique and Applications
Update: January 2004
Ce texte en français.
List of publications
Logic and graphs : General orientation and open questions
The representation of the graphs by relational structures makes it possible
to write formally their properties by means of logical formulas.
One can thus classify the properties of graphs according to the syntactic
structure of the formulas which represent them. This approach extends to
hypergraphs and relational structures.
It follows that complexity classes can be described in logical termss, independently of the definitions initially given in terms of Turing machines. In addition, polynomial algorithms and sometimes linear ones, can be obtained by effective constructions from logical formulas for certain types of graphs.
The logical languages which fit well to this approach are first-order logic, its extensions by fixed point operators and monadic second-order logic (MS). Indeed, model checking problems, optimization problems (like determining the length of a shorter path in a graph satisfying such or such property), counting problems (like counting the number of shorter paths having such or such property) formulable in MS logic have polynomial and even linear algorithms, for graphs and other structures given by a hierarchical structuring.
This approach works mainly for graphs which one can structure hierarchically, either by means of tre-decompositions introduced by Robertson and Seymour, or by means of modular decompositions, or by decompositions in terms of complete bipartites graphs.
These concepts are essential in the theory of grammars of graphs: the hierarchical structuring corresponds to the syntactic trees of classical theory of languages and monadic second-order logic yields recognizable sets (recognizability is defined in terms of congruences having a finished number of classes, in the absence of any notion of finite-state automaton having good properties).
This approach can extend to combinatorial structures more complex than graphs, in particular combinatorial maps which are graphs enriched with relations which define (up to homeomorphism) planar representations of graphs with or without crossings of edges.
In addition, as well for the algorithmic applications as for the development of theoretical bases, it is necessary to study transformations of structures and their "compatibility" with the quoted above logical languages. Two concepts are essential, that of an MS-definable transduction of structures, (the term "transduction" refers to the theory of the languages), i.e., that one can specify by formulas of MS logic, and that of MS-compatible transduction, i.e., Transformations such that the MS properties of the object structure are exprimable by MS formulas in the given structure. This notion gives an algorithmic reduction for the MS theory of the output structures to the MS theory of the input structures. Any MS-definable transduction is MS-compatible but the converse is not true.
This general framework raises many questions. The references are numbered as in the main page.
I) The expressive power of MS logic.
The question is to determine the power of MS logic for expressing
properties of graphs, of combinatorial structures such as combinatorial
maps, hypergraphs, as well as transformations of such structures.
Most questions originate from the theory graphs (and their drawings)
and of verification ("model-checking").
The obvious writing of a graph property does not give in general an MS formula or a formula of related languages. It is necessary to use particular properties of the graphs considered (like colorability, special orientations, excluded configurations, etc...) to obtain MS logical formulas.
For countably infinite graphs, some constructions relative to finite graphs do not extend easily.
Another topic is the study of partial specifications of planar graph drawings, from the algorithmic and logical points of view.
Open questions and research topics:
Q1: Is the class of the "sketches" (certain logical structures representing the graph drawings with edge crossings) definable by an MS formula? See M9.
Q2: Structure and algorithmics of partial maps: V. Dussaux' s dissertation.
Q3: Application of oriented matroids to the study of arrangements of pseudolines. See T4; thesis of E Gioan.
Q4: Which operations on graphs and relational structures yield "evaluations" (mappings from syntactic trees to the corresponding graphs ) that are MS-definable, or only MS-compatible?
Q5: Do there exist transformations of graphs or structures which are MS-compatible without being expresible as compositions of "tree expansions" (as defined by Shelah, Stupp, Muchnik and Walukiewicz) and of MS-definable transductions?
II) Hierarchical structurings of the graphs
This research topic concerns the logical, combinatorial and algorithmic
study of hierarchical structurings of graphs, which are essential
for the construction of efficient algorithms.
In particular, the decomposition of a graph into a tree-gluing of complete bipartites graphs (which gives the notion of clique-width (cwd) of graphs) raises problems of characterization by forbidden configurations and of complexity (it is not known whether the verification that a graph has a given clique-width is polynomial). The extension of this concept to the relational structures and hypergraphs remains to be explored.
The logical definissability of these structurings is also an open problem.
The extension to the relational structures and hypergraphs of modular decompositions is also an important problem for grammatical and algorithmic applications.
It motivates the study of operations on relational structures combining of basic operations like disjoint union, taking quotient by MS-definable equivalence relations and transformations by redefinition of relations by means of formulas without quantifiers.
Another manner of exploiting the existence of a tree structuring, consists in implementing a graph with n vertices by associating with each vertex a piece of information of size O(log(n)) so that fixed properties of a pair of vertices (or simply their distance) can be evaluated by using only the information attached to the given vertices. This is possible for graphs of bounded clique-width and MS expressible properties and functions.
Research questions and topics:
Q' 1: Is the recognition of graphs of cwd at most k, or of cwdl (linear clique-width) at most k is a polynomial problem?
Q' 2: How large can be the cwd (of the cwdl) of a graph in terms of its size ? And of other parameters like trre-width, path-width, diameter ?
Q' 3: A graph property, a graph optimization function exprimable in MS logic are evaluable in time O(A(k)n) on graphs with n vertices and twd at most k, given by an appropriate tree-decomposition. One should analyze the growth of the A(k) for various interesting properties of graphs, and if possible connect it to the syntax of the MS formula which defines it. One may hope to obtain interesting complexities for graphs whose twd is not necesarily bounded but is at most O(log(n)).
Q' 4: Find good heuristics for the calculation of cwd.
Q' 5: If in a graph one removes a vertex or an edge, how much can its cwd increase?
Q' 6: Find reductiuon rules which characterize graphs of cwd at most k.
On cwd see T3. See also M6-M8 for algorithmic applications.
Q' 7: Which are the minimal graphs (for the relation of induced subgraph) of cwd at least k? For k = 3 there is only P4. For k = 4 there are infinitely many. Can one give for them a grammatical or a logical characterization.
Q' 8: Certain problems have polynomial algorithms on the interval graphs, or on chordal graphs which are not of bounded cwd. Do these problems have a common logical form?
Q' 9: Can one bound the cwd of a finite graph built with p labels, the corresponding operations of label renamings and vertex fusion, and the edge redefinitions by quantifier free formulas. It is known that a bound exists by M12.
Q' 10: Answer to Q' 9 for countably infinite graphs.
Q' 11: Which properties can be implemented in graphs of bounded cwd, with information of size O(log(n)), of size O(log(n)**2) attached to vertices ? (Partial results in M13).
III) A conjecture by D. Seese
A third broad topic consists in proving or disproving a conjecture by D.
Seese, established in several particular cases, according to which:
the only sets of graphs whose monadic theory is decidable are those having bounded cwd. See articles and lectures M10, M11, and OC13 for partial results.
Q"1: This conjecture is true for directed graphs if and only if it is true for undirected graphs. Does its validity imply its validity for the directed hypergraphs (i.e., relational structures, for an appropriate extension of cwd) ?
Q"2 : Can one prove it for particular families of graphs: comparability graphs, interval graphs, families of graphs defined by excluded induced subgraphs?
Key words describing the scientific context:
Descriptive complexity, graph, hierarchical structuring of graphs, algorithmic applications, graph grammars, operations on graphs, recognizability.
This research field can be gathered in three broad topics.
1) Delimitation of the expressive power of monadic second-order logic and and related languages for expressing properties of graphs, relational structures, hypergraphs, as well as transformations of such structures. Interesting questions arise from the theory of graphs and their drawings, and from model-checking.
The logical writings use particular graph properties : colorability, special orientations, excluded configurations to name a few.
2) Logical, combinatorial and algorithmic study of hierarchical structuring of the graphs, that are essential for the construction of low complexity (and even better, tractably efficient) algorithms. The decomposition of a graph as a tree-gluing of complete bipartite graphs and cliques raises problems of characterization in terms of logic or forbidden configuration, and of algorithmic complexity. The extension of this concept (clique-width) to relational structures and hypergraphs remains to be explored.
3) A third topic is to prove a conjecture of D. Seese, according to which the only sets of graphs whose monadic theory is decidable are those having bounded clique-width.
Research activities of Bruno
Labri Group working on Logic, Automata, Algorithms and Applications.