Publications - Publications 2009
- Publications 2010
- Publications 2011
- Publications 2012
- Publications 2013
- Publications à paraitre
- Software
Réunions Problèmes Participants |
## Problem 1 : Parameterized $P_l$-edge deletion problemInput: A graph $G = (V, E)$. Parameter: integer $k$. Question: Is there a subset $F \subseteq E$ with $|F| \leq k$ such that the graph $H = (V, E \backslash F)$ is $P_l$-free? Kernel of size $O(k^3)$ for $l = 4$. No polynomial kernel for $l \geq 12$. Open problem: - What if $5 \leq l \leq 11$?
[GPP10] S. Guillemot, C. Paul and A. Perez. On the (non-)existence of polynomial kernels for Pl -free edge modification problems. In International Symposium on Parameterized and Exact Computation - IPEC. Number 6478 in Lecture Notes in Computer Science, pages 147--157, 2010. ## Problem 2 : $\Pi$-edge contraction.Input: A graph $G = (V, E)$. Parameter: integer $k$. Question: Is there a subset $F \subseteq E$ with $|F| \leq k$ such that the graph $H$ obtained by contracting the edges of $F$ belongs to class $\Pi$? When $\Pi$ is the class of: - Paths: linear kernel;
- Trees: no polynomial kernel;
- Bipartite graphs: FPT;
- Cycles: FPT.
Open problems: - Linear kernel for bipartite graphs?
- Linear kernel for cycles?
[?] B. Lévêque ## Problem 3 : Rooted triplet inconsistency :## Problem 4 : Pattern Motif :## Problem 5 : $C_k$-subdivision :Input: A digraph $D = (V, A)$. Parameter: integer $k$. Question: Does $D$ contain a $C_k$-subdivision? Open problem: - Is it FPT?
## Problem 6 : Minimum dominating sets :## Problem 7 : Greedy colouring.A Greedy colouring is a colouring obtained by taking an ordering ($v_1, v_2, \ldots , v_n$) of the vertices of $G$ and applying the greedy algorithm. (i.e. color vertex $v_i$ with the smallest colour that is not assigned to one of its neighbours). The Grundy number of $G$ is the maximum number of colors of a Greedy colouring. For fixed $k$, one can decide in polynomial time if the Grundy number of $G$ is at least $k$. It is sufficient to check if $G$ contains one of the graphs called $k$-atoms as induced subgraph [Zak06]. There is a fixed number $f(k)$ of $k$-atoms and they are of size at most $2^k$ Deciding if the Grundy number of $G$ is at least $|V(G)| - k$ (the dual problem) is FPT [HS10]. Open problem: - Is Grundy number FPT? (with $k$ as parameter)
- Does the Dual of Grundy number admits a polynomial kernel?
[Zak06] M. Zaker. Results on the Grundy chromatic number of graphs. [HS10] F. Havet and L. Sampaio. On the Grundy number of a graph. In Proceedings of the International Symposium on Parameterized and Exact Computation(IPEC), number 6478 of Lecture Notes on Computer science, December 2010. |

Page last modified on February 21, 2011, at 03:34 PM