Recent Changes - Search:

Publications

Réunions

Problèmes

Participants

PmWiki

pmwiki.org

edit SideBar

Problems2

Problems.Problems2 History

Hide minor edits - Show changes to markup

February 21, 2011, at 03:34 PM by 138.96.199.100 -
Changed lines 83-85 from:

Problem 7 : Grundy colouring.

A Grundy 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.

to:

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.

Changed line 87 from:

The Grundy number of $G$ is the maximum number of colors of a Grundy colouring.

to:

The Grundy number of $G$ is the maximum number of colors of a Greedy colouring.

February 21, 2011, at 03:28 PM by 138.96.199.100 -
Changed line 77 from:

Problem 6 : minimum dominating sets :

to:

Problem 6 : Minimum dominating sets :

February 21, 2011, at 03:28 PM by 138.96.199.100 -
Deleted lines 78-79:

Open problem:

  • Is the number of minimum dominating sets of a graph on $n$ vertices $15^{n/6}$?
Added line 101:
February 21, 2011, at 03:27 PM by 138.96.199.100 -
Added lines 83-104:

Problem 7 : Grundy colouring.

A Grundy 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 Grundy 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.

February 21, 2011, at 03:11 PM by 138.96.199.100 -
Changed lines 76-77 from:

Problem 6 : Pattern Motif :

to:

Problem 6 : minimum dominating sets :

Open problem:

  • Is the number of minimum dominating sets of a graph on $n$ vertices $15^{n/6}$?
Deleted lines 83-162:

Problem 7 : minimum dominating sets :

Open problem:

  • Is the number of minimum dominating sets of a graph on $n$ vertices $15^{n/6}$?

Problème 3 : Gendarmes et voleur :

Soit G=(V,E). Jeu à tour de rôle (deux joueurs). Le joueur 1 place ses k gendarmes, le joueur 2 place le voleur. Chacun à son tour, le joueur 1 bouge chaque gendarme (il reste sur place ou va sur un sommet voisin) puis le joueur 2 bouge le voleur. Le but pour le joueur 1 est de capturer le voleur (i.e. mettre un gendarme sur la même case que le voleur) et le but du voleur est d'échapper indéfiniment aux gendarmes.

Le cop-number d'un graphe G, noté cn(G), est le nombre minimum de gendarmes nécessaires pour capturer le voleur.

Est-ce que cn(G)=O(n1/2) pour tout graphe G? La meilleure borne supérieure connue est cn(G)=O(n/log(n)).

Si G est planaire on sait que cn(G) ≤ 3. Cela peut-il se généraliser à cn(G) ≤ g+3 pour les graphes de genre g ? On sait que cn(G)≤1,5g+3.

De plus, on sait que trouver le cop-number d'un graphe est un problème NP-hard. Mais appartient-il à NP ?

Enfin, il existe des versions où les gendarmes et le voleur peuvent se déplacer à des vitesses différentes. Par exemple, si le voleur a vitesse 2 (il se déplace à chaque tour vers des sommets à distance au plus 2) et les gendarmes ont vitesse 1 que peu-on dire sur le nombre minimum de gendarmes nécessaires? Dans le cas où G est une grille par exemple?


Problème 4 : Algorithme exact de coloration des arêtes.

L' indice chromatique d'un graphe est le plus petit nombre de couleurs d'une coloration des arêtes. D'après le théorème de Vizing, l'indice chromatique est égal au degré maximum ou au degré maximum plus un. Il est cependant NP-complet [Hol81] de décider à laquelle de ces deux valeurs il est égal.

Par l'algorithme général de coloration de Bjorklund-Husfeld et Koivisto appliqué au line-graphe de G, cela peut se décider en temps O*(2|E(G)|). Peut-on cependant faire mieux? Dans le cas ou G est cubique, il existe un algorithme en ???. Quid dans le cas des graphes 4-réguliers?

[Hol81] I. Holyer. The NP-completeness of edge-coloring. SIAM J. Computing 2:225–231, 1981.


Problème 5 : Coloration par listes des graphes d'intervalles.

Le problème consiste à trouverle meilleur algorithme qui étant donnés un graphe d'intervalles G et une assignation de listes L répond s'il existe une L-coloration de G ou pas. Le meilleur algorithme actuel fonctionne en O*(2n). Existe-t-il un algorithme en O*(cn) pour un c<1 ?


Problème 6 : Coloration des aretes d'un graphe complet.

L'index chromatique d'un graphe G, noté X'(G), est le plus petit nombre de couleurs nécessaire à une coloration propre des arêtes de G, deux arêtes devant recevoir une couleur différente lorsqu'ellesd sont adjacentes.

Calculer cet index pour les graphes complets est un problème résolu de longue date :

  • Les graphes K_2n sont de nombre chromatique Delta(G)
  • Les graphes K_{2n+1} sont de nombre chromatique Delta(G)+1

Beaucoup de conjectures tournent autour de colorations des arêtes des graphes complets ayant certaines proprietes (par exemple, celle l'union de toute paire de classes de couleur définit un cycle hamiltonien : perfect 1-factorization conjecture)... En général, elles semblent indiquer que quantité de colorations (en oubliant les colorations isomorphes) existent, mais jusqu'a présent il n'est possible d'en trouver qu'une seule dans la littérature : celle des tournois de round-Robin ( http://en.wikipedia.org/wiki/Round-robin_tournament ).

En résumé :

  • Les graphes complets sont des graphes --tres-- simples.
  • Les conjectures autour de ses colorations d'arête ne manquent pas.
  • Il serait tres agréable de pouvoir exhiber la structure de plus d'une seule coloration
February 21, 2011, at 03:10 PM by 138.96.199.100 -
Changed line 85 from:
  • Is #MDS = $15^{n/6}$?
to:
  • Is the number of minimum dominating sets of a graph on $n$ vertices $15^{n/6}$?
February 21, 2011, at 03:08 PM by 138.96.199.100 -
Added lines 80-87:

Problem 7 : minimum dominating sets :

Open problem:

  • Is #MDS = $15^{n/6}$?

February 21, 2011, at 03:04 PM by 138.96.199.100 -
Changed lines 17-22 from:

Open problems: 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 ? ? ? in Lecture Notes in Computer Science, pages ? ? ?- ? ? ?, 2010.

to:

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.

Changed lines 25-43 from:

Problème 2 : Coloration gloutonne.

Une coloration gloutonne est une coloration obtenue à partir d'un ordre (v1, v2, ... , vn) en appliquant l'algorithme glouton. (i.e. pour i de 1 à n, on colore vi avec le plus petit entier non attribué à ses voisins). Le nombre Grundy est le nombre maximum de couleurs d'une coloration gloutonne.

Pour tout k fixé, décider si le nombre Grundy d'un graphe est au plus k est polynomial. Il suffit pour cela de tester si G contient un des graphes appelés k-atomes comme sous-graphe induit. Voir [Zak06]. Il y a un nombre borné f(k) de k-atomes et ils sont tous de taille au plus 2k. Ainsi l'algorithme fonctionne en O*(n2^k).

Le problème du nombre Grundy est donc dans XP (avec la paramétrisation canonique). Mais est-il FPT? Est-il W[i]-hard?

Peut-on trouver un algorithme exact meilleur que celui donné ci-dessus en O*(n2^k)?

[Zak06] M. Zaker. Results on the Grundy chromatic number of graphs. Discrete Math. 306(23):3166–3173, 2006.

to:

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

Added lines 49-80:

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 : Pattern Motif :


February 21, 2011, at 02:45 PM by 138.96.199.100 -
Changed line 18 from:

What about when $l = \

to:

What if $5 \leq l \leq 11$?

February 21, 2011, at 02:44 PM by 138.96.199.100 -
Changed lines 3-10 from:

Problème 1 : Nombre de séparateurs minimaux.

Soit G=(V,E). Un sous-ensemble S de V est un séparateur minimal, s'il existe 2 composantes connexes C,D de G-S telles que N(C)=N(D)=S.

Quel est le nombre maximum de séparateurs minimaux dans un graphe d'ordre n ?

En considérant un graphe ayant deux sommets u et v reliés par n/3 chemins indépendants de longueur (nombre d'arêtes) 4, on obtient une borne inférieure de 3n/3. Si S est un séparateur minimal alors l'un des enembles S, C et D est de taille au plus n/3. On a donc une borne supérieure simple en \Sum_{i=1}^{n/3} C(i,n). La meilleure borne supérieure actuelle due à Fomin et Villanger est de 1.6181n

to:

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 problems: What about when $l = \

[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 ? ? ? in Lecture Notes in Computer Science, pages ? ? ?- ? ? ?, 2010.

February 21, 2011, at 02:38 PM by 138.96.199.100 -
Added lines 1-104:

(:notitle:)

Problème 1 : Nombre de séparateurs minimaux.

Soit G=(V,E). Un sous-ensemble S de V est un séparateur minimal, s'il existe 2 composantes connexes C,D de G-S telles que N(C)=N(D)=S.

Quel est le nombre maximum de séparateurs minimaux dans un graphe d'ordre n ?

En considérant un graphe ayant deux sommets u et v reliés par n/3 chemins indépendants de longueur (nombre d'arêtes) 4, on obtient une borne inférieure de 3n/3. Si S est un séparateur minimal alors l'un des enembles S, C et D est de taille au plus n/3. On a donc une borne supérieure simple en \Sum_{i=1}^{n/3} C(i,n). La meilleure borne supérieure actuelle due à Fomin et Villanger est de 1.6181n


Problème 2 : Coloration gloutonne.

Une coloration gloutonne est une coloration obtenue à partir d'un ordre (v1, v2, ... , vn) en appliquant l'algorithme glouton. (i.e. pour i de 1 à n, on colore vi avec le plus petit entier non attribué à ses voisins). Le nombre Grundy est le nombre maximum de couleurs d'une coloration gloutonne.

Pour tout k fixé, décider si le nombre Grundy d'un graphe est au plus k est polynomial. Il suffit pour cela de tester si G contient un des graphes appelés k-atomes comme sous-graphe induit. Voir [Zak06]. Il y a un nombre borné f(k) de k-atomes et ils sont tous de taille au plus 2k. Ainsi l'algorithme fonctionne en O*(n2^k).

Le problème du nombre Grundy est donc dans XP (avec la paramétrisation canonique). Mais est-il FPT? Est-il W[i]-hard?

Peut-on trouver un algorithme exact meilleur que celui donné ci-dessus en O*(n2^k)?

[Zak06] M. Zaker. Results on the Grundy chromatic number of graphs. Discrete Math. 306(23):3166–3173, 2006.


Problème 3 : Gendarmes et voleur :

Soit G=(V,E). Jeu à tour de rôle (deux joueurs). Le joueur 1 place ses k gendarmes, le joueur 2 place le voleur. Chacun à son tour, le joueur 1 bouge chaque gendarme (il reste sur place ou va sur un sommet voisin) puis le joueur 2 bouge le voleur. Le but pour le joueur 1 est de capturer le voleur (i.e. mettre un gendarme sur la même case que le voleur) et le but du voleur est d'échapper indéfiniment aux gendarmes.

Le cop-number d'un graphe G, noté cn(G), est le nombre minimum de gendarmes nécessaires pour capturer le voleur.

Est-ce que cn(G)=O(n1/2) pour tout graphe G? La meilleure borne supérieure connue est cn(G)=O(n/log(n)).

Si G est planaire on sait que cn(G) ≤ 3. Cela peut-il se généraliser à cn(G) ≤ g+3 pour les graphes de genre g ? On sait que cn(G)≤1,5g+3.

De plus, on sait que trouver le cop-number d'un graphe est un problème NP-hard. Mais appartient-il à NP ?

Enfin, il existe des versions où les gendarmes et le voleur peuvent se déplacer à des vitesses différentes. Par exemple, si le voleur a vitesse 2 (il se déplace à chaque tour vers des sommets à distance au plus 2) et les gendarmes ont vitesse 1 que peu-on dire sur le nombre minimum de gendarmes nécessaires? Dans le cas où G est une grille par exemple?


Problème 4 : Algorithme exact de coloration des arêtes.

L' indice chromatique d'un graphe est le plus petit nombre de couleurs d'une coloration des arêtes. D'après le théorème de Vizing, l'indice chromatique est égal au degré maximum ou au degré maximum plus un. Il est cependant NP-complet [Hol81] de décider à laquelle de ces deux valeurs il est égal.

Par l'algorithme général de coloration de Bjorklund-Husfeld et Koivisto appliqué au line-graphe de G, cela peut se décider en temps O*(2|E(G)|). Peut-on cependant faire mieux? Dans le cas ou G est cubique, il existe un algorithme en ???. Quid dans le cas des graphes 4-réguliers?

[Hol81] I. Holyer. The NP-completeness of edge-coloring. SIAM J. Computing 2:225–231, 1981.


Problème 5 : Coloration par listes des graphes d'intervalles.

Le problème consiste à trouverle meilleur algorithme qui étant donnés un graphe d'intervalles G et une assignation de listes L répond s'il existe une L-coloration de G ou pas. Le meilleur algorithme actuel fonctionne en O*(2n). Existe-t-il un algorithme en O*(cn) pour un c<1 ?


Problème 6 : Coloration des aretes d'un graphe complet.

L'index chromatique d'un graphe G, noté X'(G), est le plus petit nombre de couleurs nécessaire à une coloration propre des arêtes de G, deux arêtes devant recevoir une couleur différente lorsqu'ellesd sont adjacentes.

Calculer cet index pour les graphes complets est un problème résolu de longue date :

  • Les graphes K_2n sont de nombre chromatique Delta(G)
  • Les graphes K_{2n+1} sont de nombre chromatique Delta(G)+1

Beaucoup de conjectures tournent autour de colorations des arêtes des graphes complets ayant certaines proprietes (par exemple, celle l'union de toute paire de classes de couleur définit un cycle hamiltonien : perfect 1-factorization conjecture)... En général, elles semblent indiquer que quantité de colorations (en oubliant les colorations isomorphes) existent, mais jusqu'a présent il n'est possible d'en trouver qu'une seule dans la littérature : celle des tournois de round-Robin ( http://en.wikipedia.org/wiki/Round-robin_tournament ).

En résumé :

  • Les graphes complets sont des graphes --tres-- simples.
  • Les conjectures autour de ses colorations d'arête ne manquent pas.
  • Il serait tres agréable de pouvoir exhiber la structure de plus d'une seule coloration
Edit - History - Print - Recent Changes - Search
Page last modified on February 21, 2011, at 03:34 PM