Workshop on Graph Decomposition: Theoretical, Algorithmic and Logical Aspects

October 18-22, 2010

CIRM, 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:
  • 9h45: Opening session
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.
  • 18h30: Archontia Giannopoulou (National and Kapodistrian University of Athens)
    "Fast Trinity Lemma"
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.

Joint work with D. Thilikos

Tuesday 19th:
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:
  • a linear time algorithm of Frick and Grohe for deciding FOL properties of planar graphs,
  • an almost linear-time algorithm of Frick and Grohe for deciding FOL properties for classes of graphs with locally bounded tree-width,
  • a fixed parameter algorithm of Dawar, Grohe and Kreutzer for deciding FOL properties for classes of graphs locally excluding a minor, and
  • a linear-time algorithm of Nesetril and Ossona de Mendez for deciding Sigma_1-properties for classes of graphs with bounded expansion.
Joint work with Zdenek Dvorak and Robin Thomas
  • 11h00: Remy Belmonte (Bergen University) 
    "A Unified Approach for Solving Vertex Partitioning Problems in Polynomial Time"

  • 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.
  • 11h30: Jan Obdrzalek (Masaryk University, Brno)
    "On Digraph Width Measures"

  • 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
  • 11h30: Reinhard Pichler (Technische Universität Wien)
    "Bounded Treewidth in Knowledge Representation and Reasoning"

  • 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.
  • 18h30: Eugenie Foustoucos (AUEB, MPLA, Athens)
    "Automata for evaluating Existential Monadic Second-order Logic on the class of finite graphs" 
    We propose a new approach to the Monadic Second-order Logic evaluation problem on graphs consisting in reducing the problem to a corresponding problem on words. Our reduction concerns the existential fragment of Monadic Second-order Logic and it is presented for the class of all finite undirected graphs.

    More precisely, we interpret finite graphs (viewed as structures over the signature S_G={edge}) into finite colored words. We call these words graph-words and view them as structures over the signature S_W={succ, P_0, P_1, P_2, P_3} (where "succ" denotes the successor relation and the P_i's denote subsets of elements). To every graph G corresponds a unique graph-word W_G such that for every S_G-formula φ(x_1,...,x_n, X_1, ..., X_m) of existential Monadic Second-order Logic we can define a S_W-formula φ_I(x_1,...,x_n, X_1,..., X_m) which (when evaluated in the graph-word W_G of G) expresses the meaning that φ has on G. Therefore we reduce the problem of evaluating existential Monadic Second-order Logic formulas on graphs into the problem of evaluating Monadic Second-order Logic formulas on graph-words. The evaluation is performed via a new word automaton that we call assignment automaton and which acts as a computing device and not as a language recognizer: more precisely, for each existential Monadic Second-order Logic formula φ on graphs we define an assignment automaton, which, when running on the graph-word W_G of graph G, computes the satisfying assignments of φ on G. We consider datalog, the query language for deductive databases, as a tool providing algorithms for the evaluation of assignment automata on graph-words.

    We compare our approach with automata-theoretic methods that are applied to graphs of bounded tree-width and discuss some complexity issues.
Friday 22th:
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).