## Projet ANR graal - Réunions## "Décompositions de Graphes et Algorithmes"Accueil | Réunions | Participants | Publications | Contacts22-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"
- 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. |