Workshop on Graph Decomposition: Theoretical, Algorithmic and Logical AspectsOctober 18-22, 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 sub-exponential time parameterized algorithms for
problems on H-minor 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
domination-type problems in graphs are solvable in O(2^{3k}poly(n))
time for parameter boolean-width (Bui-Xuan, Telle, Vatshelle) and 2) a
decomposition of boolean-width O(log n) can be computed in
polynomial-time 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 H-coloring problems
are equivalent, on C, with the satisfaction of some first-order formula?
We
present a linear-time algorithm for deciding first-order logic (FOL)
properties in classes of graphs with bounded expansion. Many natural
classes of graphs have bounded expansion: graphs of bounded tree-width,
all proper minor-closed 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 linear-time algorithm for deciding FOL properties in classes
of graphs with locally bounded expansion; those include classes of
graphs with locally bounded tree-width 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 NP-hard 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 boolean-width 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, k-Coloring and many other problems are polynomial time solvable on these graph classes. We extend these results to d-neighbourhoods 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 H-Cover, H-Role Assignment and H-Partial 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. DAG-width, Kelly-width or bi-rank-width to name just few), but none of them has been considered to be the 'right' counterpart of tree-width, 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 tree-width. In the second part we ask whether there can be a digraph width measure which shares all the 'nice' properties of tree-width, 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
XP-time algorithms for graph problems parameterized by the rank-width
(linear rank-width) and the bi-rank-width 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 tailor-made 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 "single-exponential"). 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 single-exponential 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 n-vertex 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 brute-force 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 NP-complete 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 Second-Order
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 automata-theoretic 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, custom-made algorithms have been recently developed for some of the aforementioned reasoning tasks. They are based on a dynamic programming approach and work by a bottom-up 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
second-order logic (MSO) can be decided in linear time on any
class of graphs of bounded tree-width, or in other words, MSO is
fixed-parameter tractable in linear time on any such class of graphs,
where the parameter is the tree-width and the size of the
formula. From a logical perspective, Courcelle's theorem
establishes a sufficient condition, or an upper bound, for
tractability of MSO-model 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 tree-width 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 MSO-model checking is not fixed-parameter 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 tree-width.
The
study of pattern-closed 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,
unordered-modules, sesquimodules, bi-joins, digraph cuts of
F-rank-width 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
automata-theoretic and datalog-based solutions for several forms of
Monadic Second Order (MSO) evaluations problems that have linear-time
complexity over finite structures of bounded treewidth (given a
tree-decomposition 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
decomposition-automata which are non-deterministic bottom-up
tree-automata being equipped with a computing mechanism; these
automata, running over tree-decompositions of an input structure,
directly compute solutions to the considered MSO evaluation problems.
We directly define the decomposition-automata of atomic MSO formulas
and give a detailed description of the inductive construction of
decomposition automata for non-atomic MSO formulas.
We then transfer the ideas of decomposition-automata 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 monadic-datalog definability (resp. (k+1)-datalog definability) of MSO unary (resp. k-ary) queries over structures of bounded treewidth. Finally, we illustrate our approach (i.e. the construction of decomposition-automata 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 second-order 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 (PR-trees) to represent the family of
subpaths of a tree intersection models of G (i.e., when G is not a path
graph an empty PR-tree will be used). Similarly, a slight modification
to the PR-tree results in the Strong PR-tree 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 PR-tree will be used).
The concept
of generalized domination unifies well-known variants of
domination-like 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 tree-width. 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).
|