[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 K _{4}-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 K
_{4}-minor
cover problem asks whether there is a set S of at most k vertices whose
deletion results in a K_{4}-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 2 ^{k}.poly(n) time
is a folklore result. It is unlikely that Treewidth-t Vertex Deletion
can be solved in time c^{o(k)}.poly(n).
To the best of our knowledge, for every ﬁxed t, the best algorithm
known so far runs in time c^{klogk}.poly(n). But
whether the K_{4}-minor cover can be solved in single-exponential FPT time
was open. We prove that such an algorithm does exist. We ﬁrst use the iterative compression paradigm to reduce our problem to the parameterized disjoint K _{4}-minor cover, which given a K_{4}-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 K_{4}-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 iﬀ the original instance was positive. The
reduce-or-branch process involves some protrusion based reduction
rules. It turns out that the disjoint K_{4}-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 P _{l}-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 modiﬁcation 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 ) satisﬁes 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
modiﬁcation 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 ﬁnite set of forbidden induced
subgraph, then the three Π edge-modiﬁcation problems are
ﬁxed-parameter tractable. It was then natural to ask (Cai, IWPEC 2006)
whether these Π edge-modiﬁcation 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-modiﬁcation
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 P
_{4}
-free graphs (i.e. cographs). This paper provides positive and negative
results in that line of research. We prove that parameterized cograph
edge modiﬁcation problems have cubic vertex kernels whereas polynomial
kernels are unlikely to exist for P_{l }-free
graphs and C_{l} -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:
- 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.
- 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.
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 simpliﬁes 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. |
||