Talks

Home | Research | Publications | Talks | TeachingVitae
photo

[T13-3] Complexité et algorithmes paramétrés - introduction. Ecole Jeunes Chercheurs Mathématiques Informatique du GDR IM, Perpignan, France, 2013. (partie 1, partie 2, partie 3)

[T13-2] Conflict packing - linear kernels for FAST and dense RTI. Shonan Meeting on Parameterized Complexity and the Understanding, Design and Analysis of Heuristics. Shonan, Japan, 2013.

[T13-1] A single exponential FPT algorithm for the planar-F-deletion problem. GT Graphes et applications, LaBRI, 2013.

Soit F une famille de graphes. Le problème F-deletion consiste à tester s'il est possible de supprimer un ensemble d'au plus k sommets dans un graphe G pour obtenir un graphe H ne contenant pas de mineurs issus de F. Le cas F={K_2} correspond au problème Vertex Cover et F={K_3} à Feedback Vertex Set. Si la famille F contient au moins un graphe planaire le problème est nommé Planar-F-Deletion. Nous proposons un algorithme FPT en simple exponentiel pour Planar-F-deletion. Notre algorithme utilise la compression itérative, des règles de branchement et de réductions de protrusions. Le coeur de notre méthode est le calcul efficace d'une décomposition en protrusions (une décomposition utilisée dans de nombreux résultats). Nous présenterons l'algorithme et parlerons de ces conséquences.

[T12-5] Conflict packing - linear kernels for FAST and dense RTI. Research colloquium "Algorithmik und Komplexitätstheorie", TUB Berlin, 2012.

We introduce a new technique to design kernelization algorithms for parameterized problems, namely Conflict Packing. We illustrate this technique on two well-studied problems: FAST and RTI. For the former, one is given a tournament T = (V,A) and seeks a set of at most k arcs whose reversal in T leads to an acyclic tournament. While a linear vertex-kernel is already known for this problem, it requires a constant-factor approximation algorithm as a subroutine. Using the Conflict Packing, we show how to avoid this subroutine to find a so-called safe partition. In the RTI problem, one is given a set of vertices V and a dense collection R of rooted binary trees over three vertices of V and seeks a rooted tree over V containing all but at most k triplets from R. Using again the Conflict Packing, we prove that the dense RTI problem admits a linear vertex-kernel. This result improves the on the quadratic known kernel.

[T12-4] A single exponential FPT algorithm for the planar-F-deletion problem. Nyborg Graph Theory workshop, Nyborg, Denmark, 2012.

Given a familly F of graphs, the F-deletion problem consists in testing the existence of a set S of at most k vertices in an input graph G, such that G-S does not contain any H from F as  a minor. This problem generalizes a number of classical problems such as Vertex Cover, Feedback Vertex Set among others. We will describe a single exponential FPT time algorithm for the case F contains at least one planar graph, namely the parameterized planar-F-deletion problem where the parameter is the number of vertices to remove. Our algorithm is based on iterative compression, protrusion replacement techniques (as were several  previous algorithms for that problem)  and on ideas developed by Langer, Reidl, Rossmanith, Sikdar.  This is a joint work with Ignasi Sau and Eun Jung Kim

[T12-3] Algorithmics of modular decomposition. Algorithms and Permuntations workshop, Paris, France, 2012.

[T12-2] Important sets and contraction to bipartite. AGAPE workshop, Montpellier, France, 2012.

[T12-1] Méthodes de réduction des données (kernelization). Journée Algo-calcul du labex NUMEV, Montpellier, France, 2012.

[T11-1] Solving K4-minor cover in single exponential FPT time. Workshop on Graphs, optimization and width parameters - GROW. KAIST, Deajon, Korea, 2011.

Given an input graph G and an integer k, the parameterized K4-minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K4-minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can also be expressed as Treewidth-t Vertex Deletionproblems, with t=0 for the former and t=1for the latter.

It follows from the celebrated Courcelle’s theorem[2] or from the Graph Minor Theorem[6], that for every constant t, Treewidth-t Vertex Deletion is FPT. Asingle-exponential FPT algorithm for Feedback Vertex Set was developed only (somewhat) recently, while a simple branching algorithm for Vertex Cover which runs in 2k.poly(n) time is a folklore result. It is unlikely that Treewidth-t Vertex Deletion can be solved in time co(k).poly(n). To the best of our knowledge, for every fixed t, the best algorithm known so far runs in time cklogk.poly(n). But whether the K4-minor cover can be solved in single-exponential FPT time was open. We prove that such an algorithm does exist.

We first use the iterative compression paradigm to reduce our problem to the parameterized disjoint K4-minor cover, which given a K4-minor cover S of size k of a graph G seeks for a smaller K4-minor cover S' disjoint from S. Based on the structure of K4-free graphs (i.e. graphs whose blocks are series-parallel graphs) we describe a reduce-or-branch process which computes a set of so-called ”independent” instances such that one of these independent instances is positive iff the original instance was positive. The reduce-or-branch process involves some protrusion based reduction rules. It turns out that the disjoint K4-minor cover problem on an independent instance is equivalent to the vertex cover problem on a circle graphs, which is known to be polynomial time tractable.


[T10-5] On the (non-)existence of polynomial kernels for Pl-free edge modification problems. International Symposium on Parameterized and Exact Computation - IPEC. IMSC, Chennai, India, 2010.

Given a graph G = (V , E) and an integer k, an edge modification problem for a graph property Π consists in deciding whether there exists a set of edges F of size at most k such that the graph H = (V , E △ F ) satisfies the property Π. In the Π edge-completion problem, the set F of edges is constrained to be disjoint from E; in the Π edge-deletion problem, F is a subset of E; no constraint is imposed on F in the Π edge-edition problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity. When parameterized by the size k of the edge set F. It has been proved (Cai, IPL:58(4)-1996) that if Π is an hereditary property characterized by a finite set of forbidden induced subgraph, then the three Π edge-modification problems are fixed-parameter tractable. It was then natural to ask (Cai, IWPEC 2006) whether these Π edge-modification problems also admit a polynomial size kernel (i.e. any instance (G, k) can be reduced in polynomial time to an equivalent instance (G', k') with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlström (IWPEC 2009) answered this question negatively. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraph. It is a challenging question to characterized for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths and pointed out that the problem is already open in the case of P4 -free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for Pl -free graphs and Cl -free graph for large enough l.

[T10-4] Modular decomposition in kernelization. Workshop on Kernelization - WORKER. Lorentz Center, Leiden, Netherlands, 2010.

Modular decomposition is a graph decomposition technique which appears in the early 70's. Since them it has been used in many different contexts of combinatorics and algorithmic theory. More recently, modular decomposition based reduction rule leads to polynomial kernelizations for a number of parameterized problems. In this talk we will first briefly introduce the concept of modular decomposition. We'll then present an overview of its recent use in the context of kernelization. We'll end with a series of questions around the application of modular decomposition (or its generalizations) in kernelization.

[T10-3] Complexité paramétrée : des outils efficaces pour la résolution de problèmes difficiles. Journée Scientifique du LIRMM, Montpellier, 2010.

[T10-2] Distance hereditary graph, characterization and recognition. Finse Winter School on Algorithms. Finse1222, Norway, 2010.

[T10-1] Kernelization techniques, feedback arc set in tournaments and modular decomposition. Combinatorics Seminar. University of Toronto, 2010.

The existence of a fixed parameterized (FPT) algorithm for a parameterized problem is known to be equivalent to the existence of a kernelization algorithm: a polytime algorithm that reduces the parameterized instance to an equivalent instance whose size is bounded by a function of the parameter only.  The question for a FPT problem is whether or not it admits a polynomial (in the parameter) size kernel.  After a brief introduction to kernelization techniques, the talk contains two parts:
  1.  Parameterized Feedback Arc Set in Tournaments. A tournament T = (V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices.  Given a digraph on n vertices and an integer parameter k, the  Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The  Feedback Arc Set problem restricted to tournaments is known as  the  k-Feedback Arc Set in Tournaments (k-FAST) problem.  In this talk, we present a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T' on O(k) vertices.  In fact, given any fixed c > 0, the kernelized instance has at most (2+c)k  vertices. Our result improves the previous known bound of O(k^2) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST.

  2. Modular decomposition and polynomial size kernels. One of the reduction rules of our kernelization algorithm deals with the existence of a large (with respect to k) transitive module in a non reduced instance.  In the last few years, a few kernelization results have been obtained for parameterized graph modification problems such as cluster editing.  We give a brief overview of these known polynomial kernels.
[T09-2] Kernels for feeback arc set in tournaments. Dagstuhl seminar on parameterized complexity and approximation algorithms. Dagstuhl Schloss, Germany, 2009.

A tournament T = (V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices.  Given a digraph on n vertices and an integer parameter k, the  Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The  Feedback Arc Set problem restricted to tournaments is known as  the  k-Feedback Arc Set in Tournaments (k-FAST) problem.  In this paper we obtain a linear vertex kernel for k-FAST. That is,
we give a polynomial time algorithm which given an input instance $T$ to k-FAST obtains an equivalent instance T' on O(k) vertices. In fact, given any fixed c > 0, the kernelized instance has at most
(2+c)k vertices. Our result improves the previous known bound of O(k^2) on the kernel
size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST

[T09-1] Split decomposition and circle graph recognition is quasi-linear time. DIMAP Workshop on Algorithmic Graph Theory. Center for Discrete Mathematics and Applications, England, 2009.

The split-decomposition was introduced by Cunningham (under the name join decomposition) as a generalization of the important modular decomposition. Amongst its many applications are rank-width and circle graphs. This paper undertakes an investigation into its algorithmic properties in the context of graph-labelled trees, a new combinatorial ob ject which simplifies the consideration of the split-decomposition. We use them to derive an incremental characterization of the split-decomposition, and to explore its properties with respect to Lexicographic Breadth-First Search. These results culminate in a practical, quasi-linear time split-decomposition algorithm. Dahlhaus’ complicated, linear-time algorithm is currently the only faster solution for the problem.

[T08-3] An efficient split decomposition algorithm. Séminaire algorithmique, graphes et combinatoire, LIRMM, 2008.

Nous présenterons un algorithme de décomposition en coupes d'un graphe non-orienté quelconque. L'algorithme utilise le formalisme d'arbres étiquetés par des graphes pour représenter l'arbre de décomposition. La complexité quasi-linéaire est obtenue grâce à une analyse amortie utilisant des techniques de "déchargement". En autre conséquence, nous améliorons la complexité de la reconnaissance des graphes de cordes.

[T08-2] Introduction à la complexité paramétrée. Journées Combinatoire et Algorithmes du Littoral Méditérannéen - JCALM, 2008.

[T08-1] A quasi-linear time split decomposition algorithm - complexity analysis and application to circle graph recognition. Rencontres ANRs GRAAL -ENUM, Bordeaux, 2008.

Nous présenterons un algorithme de décomposition en coupes d'un graphe non-orienté quelconque. L'algorithme utilise le formalisme d'arbres étiquetés par des graphes pour représenter l'arbre de décomposition. La complexité quasi-linéaire est obtenue grâce à une analyse amortie utilisant des techniques de "déchargement". En autre conséquence, nous améliorons la complexité de la reconnaissance des graphes de cordes.

[T07-3] Split decomposition and dynamic distance hereditary graphs. First Canadian Discrete and Algorithmic Mathemathics Conference, Banff, Canada, 2007.

The problem of maintaining a representation of a dynamic graph as long as a certain property is satisfied has recently been considered for a number of properties. This paper presents an optimal algorithm for this problem on vertex-dynamic connected distance hereditary graphs: both vertex insertion and deletion have complexity O(d), where d is the degree of the vertex involved in the modification. Our vertex-dynamic algorithm is competitive with the existing linear time recognition algorithms of distance hereditary graphs, and is also simpler. Besides, we get a constant time edge-dynamic recognition algorithm. To achieve this, we revisit the split decomposition by introducing graph-labelled trees. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.

[T07-2] Interval completion with few edges. Algorithms seminar, School of Computer Science, McGill University, Montréal, Canada, 2006.

[T06-1] Algorithmic aspects of modular decomposition. Algorithms seminar, School of Computer Science, McGill University, Montréal, Canada, 2006.