Projet ANR graal - Réunions

"Décompositions de Graphes et Algorithmes"

Accueil | Réunions | Participants | Publications | Contacts

22-23 juin 2009, LIRMM (Montpellier)

Lundi 22 juin

14h-14h40: Benjamin Lévêque "Paths, trees and asteroids"

A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property.

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. We give an analogous characterisation of directed path graphs which are the intersection graphs of directed paths in a directed tree.

14h40-15h10: M. Habib and J. Stacho "A polynomial algorithm to compute a maximal clique tree with minimum number of leaves for chordal graphs"

We show that a clique tree of a chordal graph with minimum number of leaves can be found in time O(n^3). In particular, this generalizes polynomial-time interval graph recognition, and solves an open problem of I.-J. Lin, T.A. McKee, and D.B. West.

15h10-15h30: Arnaud Durand et Michel Habib "Some new complexities issues for the homogeneous sandwich problem"

Graph sandwich problems were introduced by Golumbic, Kaplan and Shamir in [GKS94] for DNA physical mapping problems and can be described as follows. Given a property P of graphs and two disjoints sets of edges E1, E3 on a vertex set V. E1 is the set of necessary edges and E3 the set of forbidden edges. Then the problem is to find a graph G on V with edge set Es having property P and such that E1 \subseteq Es and Es \cap E3 is empty.

In this talk, we exhibit a quasilinear reduction between the problem of finding a independent set of size k at least 2 in a graph and the problem of finding an homogeneous sandwich set of the same size k. Using this reduction, we prove that a number of natural (decision and counting) problems related to homogeneous sandwich sets are hard in general. We then exploit a little further the reduction and show that finding very efficient algorithms to compute small homogeneous sandwich sets would imply substantial improvement in the complexity of matrix multiplication problem.

16h00-16h30: Emilie Diot and Cyril Gavoille "On the path separability of planar graphs"

It is known that every weighted planar graph with n vertices contains three shortest paths whose removal halves the graph into connected components of at most n/2 vertices. Whether this property remains true with the use of two shortest paths only is an open problem.

We show that two shortest paths are enough for a large family of planar graphs, called face-separable, composed of graphs for which every induced subgraph can be halved by removing the border of a face in some suitable embedding of the subgraph. We also show that this non-trivial family of graphs includes unbounded treewidth graphs.

16h30-16h50: Martin Golumbic and Boi Faltings "A little lemma on treewidth"

abstract (ps file)

16h50-17h20: Frédéric Mazoit "Constructing brambles"

Given an arbitrary graph G and a number k, it is well-known by a result of Seymour and Thomas that G has treewidth strictly larger than k if and only if it has a bramble of order k + 2. Brambles are used in combinatorics as certificates proving that the treewidth of a graph is large. From an algorithmic point of view there are several algorithms computing tree-decompositions of G of width at most k, if such decompositions exist and the running time is polynomial for constant k. Nevertheless, when the treewidth of the input graph is larger than k, to our knowledge there is no algorithm constructing a bramble of order k + 2. I will give here such an algorithm.

Mardi 23 juin

9h20-10h: Anthony Perez "Modular decomposition in kernel reductions"

In the last decades, parameterized complexity has received a lot of attention. A problem is fixed-parameter tractable whenever it can be solved in time f(k).poly(n), where k is a parameter independent of the size of the input. Within this area, the notion of kernelization was widely studied and starts to become a research area by itself. A problem admits a kernel whenever there exists a polynomial-time algorithm that reduces an instance I with parameter k to a new instance (I',k') where I',k' <= g(k). The aim is to find the smallest g(k).

In this talk, we will see how to use the concept of modular decomposition to obtain kernelization algorithms, a module in a graph being a set of vertices sharing the same "outside" neighborhood. In particular, we will present quadratic (resp. cubic) vertex-kernels for several graph modification problems, namely (Bi)Cluster Editing and Closest 3-Leaf Power, using the so-called critical cliques and independent sets.

10h00-10h40: Stéphan Thomassé "Crown decompositions and kernel reductions"

11h10-11h40: Serge Gaspers "How fast can you 2-approximate the bandwidth of a graph?"

This talk is based on joint work with Martin Fürer (Pennsylvania State University) and Shiva Prasad Kasiviswanathan (Los Alamos National Laboratory).

The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every two adjacent vertices differ by at most b.

In this talk, I will present a 2-approximation algorithm for the Bandwidth problem that takes worst-case O(1.9797^n) = O(3^{0.6217 n}) time. This improves the previous best O*(3^n) time bound (the O* notation is similar to the usual big-Oh notation except that factors polynomial in n are ignored) for the same approximation ratio and the previous best 3-approximation algorithm of Cygan and Pilipczuk (Proceedings of ICALP 2009, to appear), which runs in time O*(2^n).

The algorithm decomposes the vertex set of G into ordered sets (called buckets) of (almost) equal sizes such that all edges are either between vertices in the same bucket or adjacent buckets. The idea is to find the smallest bucket size for which there exists such a bucket arrangement. The algorithm relies on a divide-and-conquer strategy, on dynamic programming and on the enumeration of vertex subsets and connected components of a graph.

11h40-12h30: Mike Fellows "Automata-Theoretic Approaches to Algorithmic Problems for Structurally-Decomposable Graphs"

Courcelle's Theorem concerning algorithmic problems for graphs of bounded

treewidth is just one example of what you can do about algorithmic problems for structurally decomposable graphs. This lecture will cover the basics, some further results, and point to some research horizons of the automata-theoretic perspective on algorithmic meta-theorems for decomposable graphs.