Research activities of Bruno Courcelle
LaBRI, (CNRS Laboratory umr 5800)
Research Group : Logique, Automates, Algorithmique and Applications
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.
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.
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.