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

— Gabor Retvari
źródło

problem wydaje się w dużym stopniu związany z doskonałymi wykresami, które są idealne, jeśli istnieje nieparzysta (anty-) dziura (nieregularny cykl nieparzystej długości co najmniej 5) [więcej na wikipedia]. dlatego zasugeruj, aby spróbować ponownie sformułować pytanie w kategoriach pytania na idealnych wykresach.

— dniu

@vzn: Nie jestem pewien, czy to mocne twierdzenie mogłoby tu pomóc.

— domotorp

Czy możemy zdecydować w P, czy każda krawędź G jest zawarta w pozbawionym akordów nieparzystym cyklu? Myślę, że to możliwe, ale nie wiem jak.

— domotorp

Mamy teraz dwa problemy. Z łatwością mielibyśmy decyzję w P, jeśli moglibyśmy dla każdej krawędzi zdecydować, czy jest to nieparzysty cykl nieparzysty. Znalazłem odniesienie , w którym stwierdzono, że pytania „Czy wykres zawiera indukowany cykl nieparzysty o długości większej niż trzy, przechodzącej przez określony wierzchołek?” oraz „Czy wykres zawiera indukowaną ścieżkę nieparzystą między dwoma określonymi wierzchołkami?” są kompletne NP, ale nie rozstrzygają w pełni naszej sprawy. Może się okazać, że pierwotny problem nie występuje w NP, ale nadal może być NP-trudny.

— Gabor Retvari

czy możesz wskazać, w której części swojego dokumentu zdefiniowałeś powyższy problem i jaką masz specyfikację w referacie? to („zmodyfikowana wersja okazała się NP zakończona”)

— od

$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$

— Hsien-Chih Chang 張顯之
źródło

Mam problem z przestrzeganiem którejkolwiek z tych redukcji. W pierwszej redukcji, jeśli dany węzeł v ma stopień, powiedzmy 5, to po redukcji staje się K_5, a ten K_5 zawiera cykl nieparzystej długości, ale nie odpowiada cyklowi parzystej długości zawierającemu v. In główna redukcja, załóżmy, że G = (V, E) gdzie V = {1,2,3,4,5}, E = {12,23,34,45,15,35}, a e = 34. G ma cykl długości 5, który przechodzi przez e, ale w G 'krawędź 34 jest pomostem i nie należy do żadnego nieparzystego cyklu, jeśli poprawnie rozumiem definicję twojej redukcji.

— Tsuyoshi Ito

e

$e$

e

$e$

e

$e$

G^{'}

$G'$

@ Hsien-ChihChang 張顯之: w każdym razie: skoro nagroda wkrótce wygasa i nie będzie mnie przy komputerze, przyznam ci teraz cenę. Bardzo dziękuję za odpowiedź, naprawdę pomogła mi myśleć o problemie na nowe sposoby. Jeśli możesz wrócić później i rozwiązać powyższe problemy, byłbym bardzo wdzięczny.

— Gabor Retvari

e

$e$

e

$e$

G^{'}

$G'$

G^{'}

$G'$

e

$e$

e

$e$

G^{'}

$G'$

e

$e$

G

$G$

— Hsien-Chih Chang 之之