Workshop on Graph Decomposition: Theoretical, Algorithmic and Logical AspectsOctober 1822, 2010CIRM,
Luminy, Marseille (France)
Supported by the French ANR project GRAAL "Décomposition de graphes et algorithmes" and the French ANR project AGAPE "Algorithmes de graphes paramétrés et exacts" Monday 18th:
Bidimensionality
theory appears to be a powerful framework for the development of
metaalgorithmic techniques. It was introduced by Demaine et al. (2005)
as a tool to obtain subexponential time parameterized algorithms for
problems on Hminor free graphs. Demaine and Hajiaghayi (2005) extended
the theory to obtain polynomial time approximation schemes (PTASs) for
bidimensional problems, and subsequently improved these results to
EPTASs. In this talk I will survey Bidimensionality theory from a fresh
viewpoint which can be used to give linear kernels for most
bidimensional problems, and to redesign the framework for obtaining
EPTASs to be more powerful, easier to apply and easier to understand.
The
runtime of an FPT algorithm can be specified by giving the values of
the parameter k that would yield an algorithm with runtime polynomial
in the input size n. For example, O(2^k + n) is polynomial for k in
O(log n) and linear for k up to log_2 n. This viewpoint is prominent in
combining recent results showing that: 1) a large class of
dominationtype problems in graphs are solvable in O(2^{3k}poly(n))
time for parameter booleanwidth (BuiXuan, Telle, Vatshelle) and 2) a
decomposition of booleanwidth O(log n) can be computed in
polynomialtime for various graph classes, like interval and
permutation graphs (Belmonte, Vatshelle). In this talk we present
results from the Master Thesis of Robert Sasak comparing 17 graph
parameters, with the aim of identifying candidates for similar results.
As
a part of their Graph Minors project,
Robertson and Seymour proved a lemma concerning the local
structure of graphs excluding a clique as a minor. This lemma is known
as "The Trinity Lemma" and asserts that every $K_{h}$minor
free graph with big enough treewidth contains a set $X$ of "few"
vertices whose removal creates a graph containing a "flat"
subdivided wall as a subgraph. This lemma was one of
the cornerstones of the polynomial time algorithm for the
disjoint paths problem, developed as a part of the same project. Since
then, many other applications of the Trinity Lemma appeared in graph
algorithm design. In this paper, we prove an improved version
of this lemma that is optimal in two ways. First, the dependance
between the treewidth and the height of the wall is linear
and, second, the size of the set $X$ is the smallest possible. Several
combinatorial and algorithmic consequences of our results are being
discussed.
Tuesday 19th:Joint work with D. Thilikos
We discuss
the following problem: Given a class C of graphs, of directed graphs
or, more generally, of relational structures, which Hcoloring problems
are equivalent, on C, with the satisfaction of some firstorder formula?
We
present a lineartime algorithm for deciding firstorder logic (FOL)
properties in classes of graphs with bounded expansion. Many natural
classes of graphs have bounded expansion: graphs of bounded treewidth,
all proper minorclosed classes of graphs, graphs of bounded degree,
graphs with no subgraph isomorphic to a subdivision of a fixed graph,
and graphs that can be drawn in a fixed surface in such a way that each
edge crosses at most a constant number of other edges. We also develop
an almost lineartime algorithm for deciding FOL properties in classes
of graphs with locally bounded expansion; those include classes of
graphs with locally bounded treewidth or locally excluding a minor.
Our results generalize and unify in particular the following:
Joint work with Zdenek Dvorak
and Robin Thomas
Dominating set is one of the most studied NPhard problems in computer science. This problem is solvable in polynomial time on various graph classes like interval graphs, circular arc graphs, permutation graphs and convex graphs. In this paper we give a common property of many graph classes on which Dominating set is known to be polynomial time solvable. In particular, we show that these graph classes have booleanwidth O(\log n). In other words we show that these graphs can be decomposed such that number of neighbourhoods across each cut of the decomposition is polynomial. With these results, we are also able to explain why Independent set, kColoring and many other problems are polynomial time solvable on these graph classes. We extend these results to dneighbourhoods in order to show that a wide range of problems known as Vertex Partitioning problems become polynomially time solvable on these graph classes. This settles, as an example, the computational complexity of problems like HCover, HRole Assignment and HPartial Cover on these graph classes, which were open questions until now. The area of structural digraph width measures received a significant attention in the last five years. Many 'width' notions for digraphs were defined (e.g. DAGwidth, Kellywidth or birankwidth to name just few), but none of them has been considered to be the 'right' counterpart of treewidth, which is universally accepted as a very useful and successful measure for undirected graphs. We report on the current state of the art in the field of digraph measures. In the first part we briefly compare the various digraph measures both among themselves, but also with respect to the ordinary treewidth. In the second part we ask whether there can be a digraph width measure which shares all the 'nice' properties of treewidth, but, on the other hand, depends on the orientation of edges. This talk is based on joint work with R. Ganian, P. Hlinenym, J. Kneis, A. Langer, D. Meister, P. Rossmanith and S. Sikdar.
We will
report on some recent and ongoing progress regarding existence of
XPtime algorithms for graph problems parameterized by the rankwidth
(linear rankwidth) and the birankwidth of the input graph.
Joint work with R. Ganian and J. Obdrzalek.
A
fundamental parameter in the design and analysis of graph algorithms is
the branchwidth of a graph, which can be seen as a measure of the
topological resemblance of a graph to a tree (similar to treewidth).
Its algorithmic importance is justified by Courcelle's theorem, stating
that graph problems expressible in Monadic Second Order Logic can be
solved in f(bw)n steps (here bw is the branchwidth and n is the number
of vertices of the input graph). As the bounds for f(bw) provided by
Courcelle's theorem are huge, the design of tailormade dynamic
programming algorithms for specific problems so that f(bw) is a simple
function, became a natural (and unavoidable) ingredient for many
results on graph algorithms. In this talk we overview a general
framework for the design and analysis of dynamic programming algorithms
for graphs embedded in arbitrary surfaces where f(bw)=2^{O(bw)} (such a
function is called "singleexponential"). Our approach combines tools
from topological graph theory and analytic combinatorics. In
particular, we introduce a new type of branch decomposition called
"surface cut decomposition", which generalizes "sphere cut
decompositions" introduced by Seymour and Thomas for planar graphs.
That way, we considerably extend the class of problems that can be
solved in running times with a singleexponential dependence on
branchwidth and unify/improve all previous results in this direction.
This is joint work with Juanjo Rué and Dimitrios M. Thilikos.
We prove that in an nvertex graph G, an induced planar subgraph of maximum size
can be found in time O(1.7347^n). This is the first algorithm breaking
the trivial Poly(n)*2^n bound of the bruteforce search algorithm for
the Maximum Induced Planar Subgraph problem. The algorithm exploits the
particular structure of optimal tree decompositions of planar graphs.
Deleting a
minimum number of vertices from a graph to obtain a proper interval
graph is an NPcomplete problem. At WG 2010 van Bevern et al. gave an
O((14k +14)^{k+1} kn^6) time algorithm by combining iterative
compression, branching, and a greedy algorithm. We show that there
exists a simple greedy O(n+m) time algorithm that solves the Proper
Interval Vertex Deletion problem on {claw,net,tent,C_4,C_5,C_6}free
graphs. Combining this with branching on the forbidden structures
claw,net,tent,C_4,C_5, and C_6 enables us to get an O(kn^6 6^k) time
algorithm for Proper Interval Vertex Deletion, where k is the number of
deleted vertices.
Wednesday 20th:
Courcelle's
Theorem states that every problem definable in Monadic SecondOrder
logic can be solved in linear time on structures of bounded treewidth,
for example, by constructing a tree automaton that recognizes or
rejects a tree decomposition of the structure. Existing,
optimized software like the MONA tool can be used to build the
corresponding tree automata, which for bounded treewidth are of
constant size.
Unfortunately, the constants involved can become extremely large  every quantifier alternation requires a power set construction for the automaton. Here, the required space can become a problem in practical applications. We present a novel, direct approach based on model checking games, which avoid the expensive power set construction. Experiments with an implementation are promising, and we can solve problems on graphs where the automatatheoretic approach fails in practice. Joint work with Joachim Kneis and Peter Rossmanith
Several forms of reasoning  like abduction, closed world reasoning,
answer set programming, or belief revision  are well known to be
intractable. In fact, many of the relevant problems are on the second
or even third level of the polynomial hierarchy. The concept of
treewidth allows us to define tractable fragments of these problems,
i.e., all these problems become tractable (actually, even solvable in
linear time), if the treewidth of the involved formulae or programs is
bounded by some constant.
The proof of these tractability results is via Courcelle's Theorem or extensions thereof. Of course, these tractability results as such do not immediately yield feasible algorithms. However, several new, custommade algorithms have been recently developed for some of the aforementioned reasoning tasks. They are based on a dynamic programming approach and work by a bottomup traversal of a tree decomposition of the formula or program. Prototype implementations have verified that these algorithms indeed work efficiently in case of low treewidth.
Thursday 21th:
Courcelle's famous
theorem states that any property of graphs definable in monadic
secondorder logic (MSO) can be decided in linear time on any
class of graphs of bounded treewidth, or in other words, MSO is
fixedparameter tractable in linear time on any such class of graphs,
where the parameter is the treewidth and the size of the
formula. From a logical perspective, Courcelle's theorem
establishes a sufficient condition, or an upper bound, for
tractability of MSOmodel checking.
Whereas such upper bounds on the complexity of logics have received significant attention in the literature, much less is known about corresponding lower bounds. The topic of this talk is to present recent results obtained on lower bounds for MSO in relation to the treewidth of graphs. More specifically, under a suitable complexity assumption, we show that if C is any class of graphs which is closed under taking subgraphs, and additionally, the treewidth of C is not bounded polylogarithmically (in fact, log^c n for some small c suffices), then MSOmodel checking is not fixedparameter tractable on C in the sense above. To obtain this result we will also present recent progress on the complexity of computing brambles, a natural obstruction to small treewidth.
The
study of patternclosed permutation classes has received a lot of
attention over the last decades in enumerative combinatorics. Only very
recently, the substitution decomposition of permutations has been
introduced in this aera of research and used for enumerative purposes.
In this talk, I shall give an introduction to the study of permutation
classes, and present some results on these objects linking substitution
decomposition and enumeration.
We
present a unifying framework for a large class of decompositions of
graphs related to modular decomposition. This includes but is not
restricted to the decompositions into splits, directed splits, clans,
unorderedmodules, sesquimodules, bijoins, digraph cuts of
Frankwidth 1 where F=Z_2 x Z_2, etc. We introduce a new decomposition
using the framework. It is specially designed for digraphs and fills an
existing gap, since it is not restrictable to undirected graphs. Its
components, that we called splitmodules, combine properties of modules
and of splits. Importantly, when restricted to undirected graphs, the
notion coincides with undirected modules, and thus constitutes a proper
generalization of modules for the directed case.
In our generic case, the decomposition tree is uniquely defined for a given graph. For its computation, we also present a unifying algorithmic framework. Our approach has two advantages. On the one hand it reduces the decomposition task  roughly a partitioning problem  to a specific vertex subset problem. On the other hand, it defines a set of sufficient properties for a decomposition to admit efficient algorithms computing the corresponding decomposition tree. Using our approach, the runtime for splitmodule decomposition is O(n^3).
We propose
automatatheoretic and datalogbased solutions for several forms of
Monadic Second Order (MSO) evaluations problems that have lineartime
complexity over finite structures of bounded treewidth (given a
treedecomposition of the structure). In particular, apart
from the MSO evaluation problem and the MSO model checking
problem we moreover consider "MSO evaluation problems involving
counting" which constitute variants of the former problems that are
defined via MSO formulas of the form φ(X) and require evaluating
the size of sets involved. To solve these problems, we introduce
decompositionautomata which are nondeterministic bottomup
treeautomata being equipped with a computing mechanism; these
automata, running over treedecompositions of an input structure,
directly compute solutions to the considered MSO evaluation problems.
We directly define the decompositionautomata of atomic MSO formulas
and give a detailed description of the inductive construction of
decomposition automata for nonatomic MSO formulas.
We then transfer the ideas of decompositionautomata into a datalog framework and we use datalog and its optimization techniques to implement the computation mechanism of decomposition automata, obtaining thus efficient evaluation procedures to compute the solutions of the considered MSO evaluations problems. Notice that since the automata construction can be completely expressed in datalog, we can directly define datalog queries that compute the solutions of the considered MSO evaluation problems (either involving counting or not). The resulting datalog programs prove the monadicdatalog definability (resp. (k+1)datalog definability) of MSO unary (resp. kary) queries over structures of bounded treewidth. Finally, we illustrate our approach (i.e. the construction of decompositionautomata together with the corresponding datalog rules that evaluate them) by applying it in order to solve VERTEX COVER and the related to it MSO evaluation problems involving counting. Joint work with Eugenie Foustoucos (AUEB, MPLA, Athens)
In this talk
we will present a simple logic (called "a logic on subobjects") which 
for graphs  is equivalent to secondorder monadic graph logic. We will
show how to inductively generate graph automata out of the formulas of
the logic. Furthermore we will report on experimental results
concerning the efficient representation and processing of the resulting
huge automata via binary decision diagrams.
For a given graph G,
we present a new data structure (PRtrees) to represent the family of
subpaths of a tree intersection models of G (i.e., when G is not a path
graph an empty PRtree will be used). Similarly, a slight modification
to the PRtree results in the Strong PRtree which, for a given graph
G, can be used to represent the family of directed paths of a directed
tree intersection models of G (i.e., when G is not a directed path
graph an empty Strong PRtree will be used).
The concept
of generalized domination unifies wellknown variants of
dominationlike problems. A generalized domination (also called
(\sigma,\rho)domination) problem consists in finding a dominating set
for which every vertex of the input graph is satisfied, given two sets
of constraints and . Very few problems are known to be W[1]hard
when restricted to graphs of bounded treewidth. We exhibit here a
large new (infinite) collection of W[1]hard problems parameterized by
the treewidth of the input graph, that is (\sigma,\rho)domination
when is a set with arbitrarily large gaps between two consecutive
elements and is cofinite (and some other technical requirements).
