Achèvement minimal du graphique à cycle impair sans accords: est-il difficile à NP?

Le problème intéressant suivant est apparu récemment dans mes recherches:

INSTANCE: Graphique .$G(V, E)$

SOLUTION: un achèvement de cycle impair sans corde, défini comme un surensemble de l'ensemble de bords E de sorte que le graphe complété G ' ( V , E ' ) a la propriété que chaque bord de G ' est contenu dans un cycle impair sans accord.$E'$$E$$G'(V, E')$$G'$

MESURE: la taille de l'achèvement, c'est-à-dire .$|E' - E|$

Jusqu'à présent, nous avons pu prouver qu'une version modifiée de ce problème est NP-complète, où au lieu d'exiger que "chaque bord de soit contenu dans un cycle impair sans accord" nous avons besoin de la propriété plus forte que "chaque bord est contenu en triangle (cycle de longueur 3) ". (Notez que ce n'est pas équivalent au problème de MINIMUM CHORDAL GRAPH COMPLETION .)$G'$

Le premier est facilement considéré comme une généralisation du second, mais jusqu'ici tous mes efforts pour le prouver ont échoué. Quelqu'un pourrait-il trouver un pointeur / référence / etc.?

Nous prouvons que le problème est NP-difficile même dans sa forme de décision, c'est-à-dire '' Le graphe d'entrée déjà un cycle impair sans fin? '' Par réduction du problème suivant:$G$

Problème P : Étant donné un graphe et une arête e ∈ E ( G ) , y a-t-il un cycle impair sans corde de longueur supérieure à 3 passant par e ?$G$$e\in E(G)$$e$

Ce problème est connu pour être NP-difficile par réduction de la '' détection de cycles pairs sans accords passant par un nœud donné '' dans la référence donnée dans l'un de vos commentaires qui est indiqué dans le paragraphe avant la section 3 en laissant et q = 2 :$p=0$$q=2$

Soit dit en passant, soit et p ≥ 0 des entiers fixes arbitraires. Les problèmes suivants sont NP-complets: un graphe G contient-il un cycle induit à travers un sommet prescrit u , de longueur p (mod q )? ...$q>1$$p\ge 0$$G$$u$$p$$q$

(Il peut y avoir une réduction de Karp, mais si nous autorisons une réduction de Cook, considérons la réduction suivante: Remplacer le nœud de degré d donné dans un sous-graphique complet de taille d avec des bords sortants appropriés. Ensuite, pour chaque bord du graphique complet, nous pouvons interroger l'oracle qui résout le problème P. Notez qu'un cycle pair sans corde passant par le nœud donné correspond à un cycle impair sans corde de longueur supérieure à 3 passant par l'un des bords du graphique complet.)

Maintenant pour la réduction principale. Étant donné une instance du problème P, nous détectons d'abord s'il y a des triangles passant par ; si c'est le cas, supprimez tous les nœuds qui forment un triangle avec e . Notez que la suppression de nœuds qui forment un triangle avec e ne supprimera aucun cycle impair sans accord passant par e (par la propriété sans accord).$e$$e$$e$$e$

Ensuite, pour chaque arête autre que e = ( u , v ) nous ajoutons un nœud auxiliaire v f et deux arêtes ( v f , u ) et ( v f , v ) . Observez que le nouveau graphe G ' a la propriété suivante:$f$$e=(u,v)$$v_f$$(v_f,u)$$(v_f,v)$$G'$

a un cycle impair sans accord de longueur supérieure à 3 passant par e si et seulement si G ' est un cycle impair sans achèvement.$G$$e$$G'$

Pour la seule direction if, cela peut être prouvé en considérant différents types d'arêtes dans . Chaque arête autre que e (y compris les arêtes nouvellement ajoutées) sera dans au moins un triangle (celui qui contient le nœud auxiliaire); et e sera dans un cycle impair sans accord en G ' car il y a un cycle impair sans accord passant par e dans G , et le cycle n'est pas supprimé pendant le processus de suppression de nœud.$G'$$e$$e$$G′$$e$$G$

$e$$e$$e$$G'$$G'$$G'$$G$