Podziel wykres na cykle rozłączne węzłów

Powiązany problem: Twierdzenie Veblena stwierdza, że „Wykres dopuszcza rozkład cyklu wtedy i tylko wtedy, gdy jest on parzysty”. Cykle są rozłączne na krawędziach, ale niekoniecznie są rozłączne w węzłach. Innymi słowy: „Zestaw krawędzi wykresu można podzielić na cykle, jeśli i tylko wtedy, gdy każdy wierzchołek ma równy stopień”.

Mój problem: Zastanawiam się, czy ktoś badał podział na grafy w cyklach rozłącznych węzłów. Oznacza to podzielenie wierzchołków wykresu na , a każdy podgrupa indukowany przez jest hamiltonianem. $V$ $G$ $V_1, V_2, \cdots, V_k$ $V_i$

Czy to trudne NP czy łatwe?

Bardziej powiązany problem: Podział na trójkąt jest zakończony NP. (Strona 68 z „Komputery i trudność”)

Z góry dziękuję za radę. ^^

cc.complexity-theory graph-theory co.combinatorics Peng Zhang
źródło

Łatwa redukcja dopasowania. Dobrze znane ćwiczenie w algorytmach.

Chandra Chekuri,

Czy to twój problem: en.wikipedia.org/wiki/Vertex_cycle_cover ?

Thomas Ahle

@ThomasAhle Dzięki, nie wiedziałem o tej stronie wiki. Nazywa się to „rozłączną okładką cyklu” wspomnianą na tej stronie wiki.

Peng Zhang

Odpowiedzi:

Podział na cykle rozłączne wierzchołków to to samo, co 2-regularny podgraph, bardziej znany jako 2-czynnik. Można go znaleźć (jeśli istnieje) w czasie wielomianowym za pomocą algorytmu opartego na dopasowywaniu. ~~Np. Zobacz ten link .~~

ETA listopad 2013: Z poniższych komentarzy wydaje się, że ograniczenie z powyższego źródła jest błędne. Jednak stwierdzenie, że problem można sprowadzić do idealnego dopasowania, pozostaje prawidłowe. Prawidłowe zmniejszenie znajduje się w WT Tutte (1954), „Krótki dowód twierdzenia o czynniku dla grafów skończonych”, Canadian J. Math. 6: 347–352 .

Zastąp każdy wierzchołek stopniem pełnym dwustronnym wykresem $v$ $d$ $G_v=K_{d,\,d-2}$ $uv$ $G_u$ $G_v$ $d$ $G_v$

$d-2$ $G_v$ $d-2$ $d$ $G_u$

David Eppstein
źródło

Nie rozumiem Wszystkie wspomniane przeze mnie wzmianki o tym algorytmie zaczynają się od obliczenia trasy euler. Istnieje jednak wiele wykresów, które można pokonywać cyklami bez wycieczki po Euler. Czy jest to również w P, jeśli nie wymagamy użycia wszystkich krawędzi?

Thomas Ahle

Czy czytałeś artykuł, do którego linkowałem? Nie widzę tam wzmianki o trasach Euler.

David Eppstein,

E^{'}

$E'$

(i, j)

$(i,j)$

V

$V$

V^{'}

$V'$

(i, j^{'})

$(i,j')$

V

$V$

V^{'}

$V'$

To znaczy, mógłbym również przekonwertować każdą nieukierowaną krawędź na skierowaną krawędź w każdym kierunku, ale wtedy dopasowanie może dać mi dużo cykli „długości 2”, nie?

Thomas Ahle,

k

$k$

k

$k$