[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:
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. |
||