ICGT 2004
International Conference on Graph Transformations
Roma, September 29 th - October 2nd, 2004
Satellite Workshop :
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
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.
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
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>,