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
P_{4}. 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**.