Minimalne ukończenie wykresu nieparzystych cykli nieparzystych: czy jest trudne NP?

W moich badaniach pojawił się ostatnio następujący interesujący problem:

INSTANCJA: Wykres .$G(V, E)$

ROZWIĄZANIE: Zakończenie akordu nieparzystego cyklu nieparzystego, zdefiniowane jako nadzbiór zestawu krawędzi tak że skompletowany wykres ma właściwość polegającą na tym, że każda krawędź w jest zawarta w bezciężkim cyklu nieparzystym.$E'$$E$$G'(V, E')$$G'$

POMIAR: Rozmiar uzupełnienia, tj..$|E' - E|$

Do tej pory udało nam się udowodnić, że zmodyfikowana wersja tego problemu jest NP-zupełna, a zamiast wymagać, aby „każda krawędź w była zawarta w bezcłowym cyklu nieparzystym ”, potrzebujemy silniejszej właściwości, że„ każda krawędź jest zawarta w trójkącie (cykl o długości 3) ”. (Zauważ, że nie jest to równoważne z problemem MINIMALNEGO WYKONANIA WYKRESU CHORDALNEGO ).$G'$

Ta pierwsza jest łatwo postrzegana jako uogólnienie drugiej, ale jak dotąd wszystkie moje wysiłki, aby udowodnić, że się nie udały. Czy ktoś może wymyślić wskaźnik / referencję / itp.?

$G$

$G$$e\in E(G)$$e$

$p=0$$q=2$

$q>1$$p\ge 0$$G$$u$$p$$q$

(Może istnieć redukcja Karp, ale jeśli pozwolimy na gotowanie, rozważ następującą redukcję: Zastąpienie węzła o danym stopniu d całkowitym podgrafem o rozmiarze d z odpowiednimi krawędziami wychodzącymi. Następnie dla każdej krawędzi na pełnym wykresie możemy zapytać wyrocznia rozwiązująca problem P. Zwróć uwagę, że bezcłowy cykl parzysty przechodzący przez dany węzeł odpowiada bezcłowy cykl nieparzysty o długości większej niż 3 przechodzącej przez jedną z krawędzi pełnego wykresu.)

$e$$e$$e$$e$

$f$$e=(u,v)$$v_f$$(v_f,u)$$(v_f,v)$$G'$

$G$$e$$G'$

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

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