• View
• Edit
• History
• Print

Problem 1 : Parameterized $P_l$-edge deletion problem

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 = (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. Discrete Math. 306(23):3166–3173, 2006.

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