 Research activities  of Bruno Courcelle

LaBRI, (CNRS Laboratory umr 5800)

Update: January 2004

Ce texte en français.

Logic and graphs : General orientation and open questions

Scientific context

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.

Research topics

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.

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.

Questions:

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?

Abstract.

Key words describing the scientific context:

Descriptive complexity, graph, hierarchical structuring of graphs, algorithmic applications, graph grammars, operations on graphs, recognizability.

Short description

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  Courcelle.

Labri Group working on Logic, Automata, Algorithms and Applications
.