ICGT 2004

International Conference on Graph Transformations

Roma, September 29 th - October 2nd, 2004

Satellite Workshop :


Logic, Graph Transformations, Finite and Infinite Structures

October 1-2, 2004


Preliminary Program

  (updated : September 27 th)




This  satellite workshop will be held on :
  Friday morning from 9h to 13h : Residenza di Ripetta , via Via di Ripetta, 231, Roma
, www.ripetta.it
This  site can be easily reached by public transportation:
underground line "A" station "Flaminio" is placed 300mt from via di Ripetta
many bus lines ( 95, 117, 119, 490, 491, 495, 590, ...) and the tramway line 2, stops around there. See the main page of ICGT.

and Saturday from 9h to 18h at a different place : Department of Computer Science,  Via Salaria 113.

It is easily reachable both from Flaminio (490, 491 or 495  bus),
Barberini (63 or 80 bus) and Termini (86, 92, 217 or 310 bus)  subway stations.

About  the program :
Special topic : Clique-width, related notions and applications
(Polynomial algorithms for Monadic Second-order expressible graph problems on graphs of bounded clique-width or, equivalently bounded rank-width.
Well-quasi ordering of graphs of bounded rank-width.
Seese’s Conjecture.)


Guest  speaker for this  topic :
Sang-il Oum, Program in Applied and Computational Mathematics
Princeton University.


This workshop is co-organized by the  GAMES Network of European Union. 

Preliminary program :

Friday  October 1st  :

9h-10h30 : B. Courcelle (10 min.) : Wellcome and presentation of the program.
P. Hlineny (45 min.) : Are matroids interesting combinatorial structures ?
D. Seese (30 min.) : Decidability and computability for matroids of bounded branch-width.

10h30-11h : Coffee Break

11h-13h : S. Oum   (45 min.) : Rank-width, Clique-width and vertex-minors.
B. Courcelle (30 min.) : Isotropic systems, monadic second-order definition of vertex-minors and Seese’s Conjecture.
D. Kratsch (30 min.) : Algorithms on (P5, gem)-free graphs



Saturday October 2nd ,

9h-10h15 : S. Oum (45 min.) :
An algorithm for recognizing rank-width < k and the well-quasi-ordering of  the vertex-minor relation.
A. Brandstädt (30 min.) : Efficient algorithms for the Maximum Weight Stable Set problem: Graph decompositions and clique-width

10h15-10h45 : Coffee Break 

10h45- 12h30  : D. Janin (45 min.) : Automata theory for distributed games
D. Caucal (30 min.) : Games on equational graphs
F. De Montgolfier (30  min.) : Beyond modular decomposition, 2-modular decompositions

12h30-14h : Lunch Break

14h-15h30 : F. Scarcello (30 min.)  : Hypertree decompositions of hypergraphs: game-theoretic and logical representations.
J. Makowsky (45  min.) : SAT related problems for clause sets of bounded clique width.

15h30-16h : Coffee Break


16h-18h : M. Rao (30  min.) : On the 2-join decomposition
E. Fisher (30 min.) : The difficulty of testing for isomorphism against a graph that is given in advance.

Last minute lectures. Exact duration will be determined on the spot.

E. Foustoucos : The MSO-evaluation problem on trees and structures of bounded tree-width: a database-theoretic approach.

Problem session (30 min.) 

B. Courcelle  (10 min.) : Concluding remarks, Future workshops, Submission of articles to journals.

18h : End of workshop.


Adresses, abstracts

From France :

Bruno Courcelle
LaBRI, Bordeaux 1 University
351 cours de la Libération
F-33405 Talence
France
courcell@labri.fr


Title : Isotropic systems, Monadic Second-order  definition of vertex-minors, and Seese’s Conjecture.

Abstract :  This lecture is related to those of S. Oum. It shows how the notion of an isotropic system and the corresponding minor relation, studied by A. Bouchet  between 1987 and 1994, can be formalized in monadic second-order logic.
The vertex-minor relation on graphs is thus expressible in C2MS logic, i.e., in monadic second-order logic augmented with the Even(X)  predicate expressing that a set X has even cardinality.
Together with results of combinatorial nature, one obtains a proof of the following result :
if a set of graphs has a decidable C2MS satisfiability problem, then it has bounded rank-width, whence bounded clique-width.
A quick review of the previously proved cases of Seese’s conjecture will be presented.

Related document : http://www.labri.fr/~courcell/ActSci.html

oOo

David Janin
LaBRI, Bordeaux 1 University
351 cours de la Libération
F-33405 Talence
France
janin@labri.fr

Title : Automata theory for distributed games

Abstract : Distributed games have been defined recently as an extension of the discrete two players games that are used in the design and analysis of computerized systems.
The purpose of this extension is to help modeling and analyzing distributed phenomena that commonly occurs in computerized systems and that are essentially absent in the two  players game model.
After a survey of the notion of distributed games and its possible  uses, we will show how classical theory of infinite tree-automata applies to the resolution of these games.
The resulting theory is better founded  into classical theoretical computer science, becomes more accessible to computer scientists, and, probably, is more easy to develop and
apply.

oOo


Didier Caucal
IRISA-CNRS
Campus de Beaulieu
F-35 042 Rennes
caucal@irisa.fr
http://www.irisa.fr/galion/caucal/

Title : Games on equational graphs

Abstract : We consider two player games on infinite structures.
The structures are the hyperedge replacement equational graphs defined by Courcelle :
these graphs are the graphs generated by the deterministic graph grammars. 
By graph grammar transformations and for several winning conditions, 
we compute the winning regions and equational uniform positional strategies.

oOo


Dieter Kratsch 
LITA, Universite de Metz
Ile du Saulcy
57045 Metz, Cedex 01
France

kratsch@sciences.univ-metz.fr

Title : The use of modular decomposition to design linear time algorithms for (P5, gem)-free graphs. 

Abstract : A graph is (P5, gem)-free, when it contains neither a P5 (an induced path with five vertices) nor a gem (the graph formed by making a universal vertex adjacent to each of the four vertices of the induced path P4 an induced subgraph.
We provide a linear time algorithm to optimally color
(P5, gem)-free graphs. We use a characterization of (P5, gem)-free graphs via their modular decomposition trees and their prime subgraphs (prime w.r.t.  modular decomposition).  
The previously best known algorithm could be obtained using the fact that
(P5, gem)-free graphs have small clique-width. Its running  time is polynomial ; however the exponent is larger than 2000. 

Related document :  http://www.labri.fr/~courcell/ICGT/Kratsch-Roma.pdf

oOo


Michael Rao
LITA, Universite de Metz
Ile du Saulcy
57045 Metz, Cedex 01
France


Title : On the 2-join decomposition

Abstract: A 2-join in a graph G=(V,E) (as defined by Fabien De Montgolfier) is a partition V',V" of V such that there is a subset W' of V' and a subset W" of V" for which the edges between V' and V" in G are exactly the edges between W' and W" or the edges between V'-W'  and V"- W". The 2-join decomposition can thus be defined as a generalization of the modular decomposition.
We present a characterization of the class of graphs that are completely decomposable by the 2-join decomposition.
We also show that the clique-width of a graph G is bounded if all the primes graphs in the split decomposition or  all the prime graphs in the 2-join decomposition of G have bounded clique-width.


Abstract:
http://www.labri.fr/~courcell/ICGT/Rao.pdf

oOo

Fabien De Montgolfier,
LIRMM, Montpellier, France
montgolfier@lirmm.fr
fm@liafa.jussieu.fr

Title : Beyond modular decomposition, 2-modular decompositions

Abstract: The modular decomposition is a well known graph decomposition that considers modules (a subset of vertices such that a vertex is  adjacent either to all or to no vertex modules). We study here how it can be extended. The known extensions (homogeneous decomposition, split decomposition) are special case of 2-modular decomposition. However, the  2-module does not fall into the partitive hypergraph decomposition frame  and so are hard to manage. Therefore we focus on special classes, like bipartite graphs or split graphs.

oOo


From USA :

Sang-il Oum,
Program in Applied and Computational Mathematics
Fine Hall, Washington Road,
Princeton University,
Princeton, NJ 08544 USA

sangil@princeton.ed



First Talk : Rank-width, Clique-width and vertex minors

Abstract :   It is an open problem to find a polynomial-time algorithm to decide whether an input graph has clique-width at most k, for fixed k.
Paul Seymour and S. Oum  propose the somewhat better notion ofrank-width, which is just a slight modification of the definition of branch-width for graphs and matroids.
A class of graphs has bounded clique-width iff it  has bounded rank-width.
Tree-width is a well-studied graph parameter and has many analogies to clique-width. The work of  Robertson and Seymour shows the  minor inclusion relation of graphs is crucial to study tree-width.
The induced subgraph relation could be similar  for clique-width, but it is not rich enough.  Instead the notion of vertex-minor is introduced. Furthermore, there has been a call for a structure theorem for large clique-width graphs, something like "excluded grid"  theorem by Robertson and Seymour. 
The relation between binary matroids with the  minor-matroid  relation, and bipartite graphs with vertex-minor relation will be presented, together with one application of the grid theorem for binary matroids by Geelen et al., which gives us a structure theorem for bipartite graphs of large clique-width, equivalently of large rank-width.
A. Bouchet introduced the notion of an isotropic system in 1987. Its relation to graphs and the notion of vertex-minor will be presented.



Second talk: An algorithm for recognizing rank-width < k and the well-quasi-ordering of  the vertex-minor relation

Abstract :   Paul Seymour and S. Oum found a fixed-parameter-tractable "approximation" algorithm for rank-width whose running time is no more than O(n10):
for fixed k, it either confirms an input graph has rank-width > k, or outputs the rank-decomposition of width at most 3k+1, so that the rank-width is at most 3k+1.
This algorithm removes a burden for the "clique-width research community":
 a k-expression is no longer required as  input, and one still gets polynomial-time algorithms. One  can generate a (3k+1)-expression if  wanted.
The well-quasi-ordering of graphs of bounded clique-width
or rank-width will be discussed. 
In an infinite list of  graphs of bounded rank-width, one is isomorphic to a vertex-minor of another.
One corollary is important : there are only finitely many excluded vertex-minors for the class of graphs of rank-width at most k.
 By combining this  with a joint work  with B. Courcelle, one can actually test the property "rank-width at most k" in polynomial time if k is fixed.
One special case of the above corollary is when k=1 because the set of graphs of rank-width at most 1 is the set of distance-hereditary graphs, and it is known that it is expressible by exactly one excluded vertex-minor.

oOo


From Italy :

Francesco Scarcello (Calabria, Italy)
D.E.I.S., Universita' della Calabria,
Via P. Bucci 41/C,
87030 Rende (CS), Italy.
http://wwwinfo.deis.unical.it/~frank

Title: Hypertree decompositions of hypergraphs: game theoretic and logical representations.

Many hard problems, such as answering database queries, solving constraint satisfaction problems, computing Nash equilibria in graphical games  are in fact easy if their structure may be represented as an acyclic hypergraph. The notion of bounded hypertree-width, based on the related notion of hypertree decomposition, generalizes the notions of hypergraph acyclicity and bounded tree-width, and corresponds to larger classes of tractable problems.
 
We provide natural characterizations of hypergraphs and queries having bounded hypertree-width in terms of game-theory and logic, and we present some possible applications of hypertree decompositions in database theory, artificial intelligence, and game theory.
 
First we define the Robber and Marshals game, and prove that a hypergraph H has hypertree-width at most k if and only if k marshals have a winning strategy on H, allowing them to trap a robber who moves along the hyperedges. This game is akin the well-known Robber and Cops game (which characterizes bounded treewidth), except that marshals are more powerful than cops: They can control entire hyperedges instead of just vertices.

 Kolaitis and Vardi recently gave an elegant characterization of the conjunctive queries having tree-width at most k in terms of the k-variable fragment of a certain logic CQF ( the existential-conjunctive fragment of positive first-order logic). We use the Robber and Marshals game to derive a surprisingly simple and equally elegant characterization of the class HWK of queries of hypertree-width at most k in terms of guarded logic. In particular, we show that HWK = GFK(CQF), where GFK(CQF) denotes the k-guarded fragment of CQF. In this fragment, conjunctions of k atoms rather than just single atoms are allowed to act as guards. For the particular case k=1, our results provide new characterizations of the class of acyclic queries.
 
We will also discuss some interesting open problems on hypertree decompositions and  related notions.

 

Related articles and preprints : http://wwwinfo.deis.unical.it/~frank/Hypertrees/
 
 

oOo


From Germany :

Detlef Seese (Karlsruhe, Germany)

Institute AIFB
University Kalrsuhe (TH)
D-76128 Karlsruhe
Germany

seese@aifb.uni-karlsruhe.de,

Title : Decidability and computability for matroids of bounded branch-width.
Joint work with Petr Hlineny


Abstract : We show that, for every finite field F, the class of all F-representable matroids of branch-width at most a given constant  has a decidable MSO theory.
In the other direction,  we prove that every class of F-representable matroids with a decidable monadic second-order theory must have uniformly bounded branch-width.
Moreover interpretability, as a uniform tool to  deduce computability of algorithmic problems, especially for matroids, is investigated.

oOo


Andreas Brandstädt
ab@informatik.uni-rostock.de

Title : Efficient algorithms for the Maximum Weight Stable Set problem: Graph decompositions and clique-width


Abstract :
The Maximum Weight Stable Set (MWS) Problem is one of the most fundamental graph problems which has many facets in different areas of graph theory and combinatorial optimization.
It is known to be NP-complete in general and on some particular graph classes, whereas it can be solved efficiently on a variety of special classes, in particular for classes of bounded clique-width, for graphs which are decomposable with respect to clique cutsets and split decomposition, and for graphs having simple prime graphs with respect to modular decomposition.
We give some new results and some simpler proofs of known results in this area

Related articles and preprints : 
http://www.informatik.uni-rostock.de/(en)/~ab/artikel.html

oOo

From  Czech Republic
P. Hlineny
Dept. of Computer Science
VSB - Technical University Ostrava
17. listopadu 15
70833 Ostrava
Czech Republic
petr.hlineny@vsb.cz

http://www.cs.vsb.cz/hlineny

Title :  Are matroids interesting combinatorial structures ?

Abstract : Matroids present strong generalization of graphs, and some recent deep results of structural matroid theory
have found important applications also back in graph theory. (Cf. the  talks by S. Oum.)
We will give a brief introduction to matroids, we will show their strong relation to graph theory, and we will discuss monadic second-order logic of matroids.
In particular, we will state that any 
monadic second-order definable property of matroids can be solved in linear time (by a tree automaton) on matroids of bounded branch-width represented over a finite field.
This topic is related to the talk by D. Seese.

Abstract.

oOo


From Israel :


Janos Makowsky
Faculty of Computer Science,
Technion - Israel Institute of Technology
Haifa, 32000 Israel

and

Department of Mathematics,
ETH Zurich, Switzerland

(On sabbatical in Zurich till 30.9.2004, D-MATH, ETHZ
CH-8092 Zurich)


janos@cs.technion.ac.il
http://www.cs.technion.ac.il/~janos

Title : SAT related problems for clause sets of bounded  clique width
(Joint work with E. Fischer, A. Magid and E. Ravve)

Abstract : We show that the characteristic polynomial of SAT can be computed in polynomial time for clause sets of clique width at most k, with constants simply exponential in k.
We also discuss which clause sets are of bounded clique width in real life applications.

Related documents (slides) : http://www.cs.technion.ac.il/~admlogic/TR/SAT/sat-slides.ps

oOo


Eldar Fisher
Computer Science Department
Technion - Israel Institute of Technology
Haifa 32000 Israel
 eldar@cs.technion.ac.il
 http://www.cs.technion.ac.il/users/eldar/

Title : The difficulty of testing for isomorphism against a graph that is given in advance

Abstract : Property testing is a fast-growing new field in computer science with many connection to combinatorial theory. One of the long standing  questions is that of characterizing the properties that admit an efficient testing algorithm as defined in this framework.
The main result presented in this talk concerns a simplified instance of this question, when the "property" of graphs to be tested for holds for exactly one graph. In other words, we would like to efficiently  test that an unknown graph is close to being isomorphic to a graph  that we know in advance.
It turns out that there is a correlation  between a simple combinatorial measure of the "complexity" of the  known graph, and the number of queries that the corresponding test requires.
 In the proof of the main result use is made of Szemeredi's Regularity  Lemma, a useful tool in graph theory that states that every graph is close in some sense to being a "patchwork" of random graphs, complete  bipartite graphs, and edgeless graphs.

The talk will include a very brief introduction to property testing, an introduction to the regularity lemma and its role in many property testing results, and a proof outline of the main result.

The article containing the main result and
general survey to property testing can be found here :
http://www.cs.technion.ac.il/users/eldar/hisg.ps
http://www.cs.technion.ac.il/users/eldar/surv.ps

oOo


From Greece :

Eugénie Foustoucos
Graduate Program in Logic, Algorithms and Computation ,
Department of Mathematics,
National and Capodistrian University of Athens,
Panepistimiopolis, 15784 Athens,
Greece,
email: aflaw@otenet.gr,
or : eugenie@math.uoa.gr


title :  The MSO-evaluation problem on trees and structures of bounded tree-width : a database-theoretic approach.

Abstract :  We consider the Monadic Second-Order evaluation problem on trees and structures of bounded tree-width in a database theory perspective :
we present two approaches for computing the satisfying assignments of a formula f in a structure L; in the first approach we construct relational algebra's expressions and in the second we construct a Datalog program using the magic-set program rewriting method.
Our method is related to the linear-time algorithm of  Flum, Frick and Grohe [in "Query evaluation via tree-decomposition"] which is based on the well-known equivalence between tree automata and MSO Logic,  and which extends (to non-boolean queries) the seminal result of B. Courcelle.
This is a joint work with Lambrini Kalantzi.


oOo

 Emails  of organizers :

Bruno Courcelle <courcell@labri.fr>,
Erich Graedel <graedel@i7.informatik.rwth-aachen.de>,
David Janin <janin@labri.fr>,


Francesco Parisi-Presicce <fparisi@ise.gmu.edu>,
H. Ehrig <ehrig@cs.tu-berlin.de>
,