Problèmes NP-difficiles sur les cographies

12

Cette question est similaire aux problèmes NP-difficiles sur les arbres :

Il existe un grand nombre de problèmes NP-complets qui sont traitables sur les cographies . Y a-t-il des problèmes connus qui restent NP-complets lorsqu'ils sont limités aux cographies?

Pour être plus précis, je suis intéressé par des exemples où la saisie consiste uniquement en une cographie non dirigée et non pondérée .

Deux remarques:

Pour les cographies pondérées, un tel problème est mentionné ici - TSP avec deux voyageurs
Les cographies sont la "classe de base" de la largeur de la clique, comme les arbres sont la classe de base de la largeur de l'arbre.

MISE À JOUR

Quelques réflexions supplémentaires (je ne suis pas tout à fait sûr): Si l'entrée est vraiment juste une cographie, la question doit être du type "La cographie a-t-elle la propriété X?". Il suffirait qu'un tel problème existe pour les arbres, car alors la question pourrait être "Le cotree de la cographie a-t-il la propriété X?".

cc.complexity-theory np-hardness graph-algorithms Martin Lackner
la source

Donc, pour éviter d'être une question (pas si) dupliquée, peut-être que nous devons également que ces problèmes NP-complets soient résolus en temps polynomial sur les arbres?

Hsien-Chih Chang 張顯之

Ce serait bien sûr bien sûr. Cependant, je serais contesté même si ce n'était pas le cas. D'autant plus que tous les exemples donnés dans le fil d'origine ne répondent pas à ma question (à ma connaissance).

Martin Lackner

11

Peut-être que mon problème ouvert préféré est intéressant: le problème de couverture de clique de bord sur les cographies. Dans le problème de couverture de clique de bord, vous voulez couvrir les bords de la cographie avec un nombre minimal de cliques. On ne sait pas si ce problème est NP-complet.

Pour illustrer que le problème est probablement difficile, soit le graphe multipartite complet avec ensembles de partites chacun de taille . Ceci est une cographie. Il existe carrés latins orthogonaux par paires d'ordre si et seulement si la couverture clique de bord de est . Cela a été démontré par Park, Kim et Sano . Il s'agit d'une formule pour le "graphique du cocktail", c'est-à-dire le cas où . $K_n^m$ $m$ $n$ $m - 2$ $n$ $K_n^m$ $n^2$ $n = 2$

Ton Kloks
la source

10

Plusieurs problèmes restent NP-complets lorsqu'ils sont limités aux cographies. La coloration de la liste, le nombre achromatique et l'isomorphisme de sous-graphique induit restent NP-complets.

[1] Hans L. Bodlaender. Le nombre achromatique est NP-complet pour les cographies et les graphiques d'intervalle. Inf. Processus. Lett., 31 (3): 135-138, 1989

[2] Klaus Jansen et Petra Scheffler. Coloration généralisée pour les graphiques arborescents. Appl. Discrète Math., 75 (2): 135-155, 1997

[3] Peter Damaschke. L'isomorphisme de sous-graphique induit pour les cographies est NP-complet. Notes de cours en informatique, 1991, Volume 484/1991, 72-78,

Mohammad Al-Turkistany
la source

1

Merci beaucoup pour votre réponse. Ce sont des problèmes vraiment intéressants, mais je pense qu'ils ne répondent pas à l'exigence selon laquelle l'entrée n'est qu'un graphique: l'entrée dans [1] est un graphique et un entier, [2] un graphique et un ensemble de couleurs pour chaque sommet, [ 3] deux graphiques.

Martin Lackner

3

Voici des variations triviales de deux des mêmes problèmes qui restent NP-complets mais qui n'ont qu'une entrée de cographie: la cographie donnée est-elle constituée de deux composants connectés, dont l'un est un sous-graphique induit de l'autre? La cographie donnée a-t-elle une coloration complète qui donne à chacun de ses sommets isolés une couleur distincte?

David Eppstein

10

$G$ $H$ $H$ $G$ $H$ $G$ $\rho: V(G)\to V(H)$ $\gamma: V(H)\to V(G)$ $\rho\circ \gamma : V(H)\to V(H)$

vb le
la source

2

Encore une fois, cela peut être réinterprété comme un problème sur une seule cographie (qui se trouve avoir deux composants connectés).

David Eppstein

1

Je vois. Bien sûr, on peut demander des problèmes NP-complets où l'entrée se compose uniquement d'une cographie connectée , non dirigée et non pondérée. Je pense que la question est assez intéressante.

le

1

G

$G$

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

| V (G_{1}) | \leq | V (G_{2}) |

$|V(G_1)|\le|V(G_2)|$

G_{1}

$G_1$

G_{2}

$G_2$

David Eppstein

Ah, ça va!

le

Problèmes NP-difficiles sur les cographies

Réponses: