Czy problem zestawu wierzchołków sprzężenia zwrotnego można rozwiązać w czasie wielomianowym dla wykresów ograniczonych do 3 stopni?

19

Sprzężenie zwrotne Zestaw wierzchołków jest NP-kompletny dla ogólnych wykresów. Wiadomo, że jest NP-kompletny dla wykresów ograniczonych do stopnia 8 ze względu na redukcję z pokrycia wierzchołków. Artykuł w Wikipedii mówi, że jest on rozwiązany w czasie wielozakresowym dla grafów związanych ze stopniem 3 i jest NP-kompletny dla grafów związanych ze stopniem 4. Ale nigdzie nie znalazłem na to żadnego dowodu. Czy to prawda?

Jaka jest minimalna wartość d, aby FVS na wykresach ograniczonych stopniem d był NP-kompletny?

cc.complexity-theory graph-theory graph-algorithms np-hardness bounded-degree Davis Issac
źródło

1

Czy ktoś wie, czy problem jest trudny na zwykłych niekierowanych grafach stopnia 4?

10

Algorytm Li i Liu jest niepoprawny (opublikowany w Chinach, choć w języku angielskim). Algorytm Ueno i in. Jest poprawny, a podobny algorytm można znaleźć w Furst i in. 1 . Oba algorytmy redukują problem do rozwiązanego przez wielomian problemu parzystości matroidów [3].

Jego redukcja w stosunku do VC zapewnia twardość NP dla wykresu związanego ze stopniem 6! Ponieważ VC jest już twarde NP na grafach sześciennych. Speckenmeyer twierdził, że jego praca [4] zawiera dowód twardości NP FVS na płaskich wykresach o maksymalnym stopniu czwartym, ale bardzo trudno ją znaleźć (bardzo docenię, czy ktoś, kto ma dostęp do jego pracy, może wysłać mi kopię ). Na szczęście nowy dowód na twardość NP wykresów z ograniczeniem stopnia czwartego można znaleźć w 2 :

Uwagi na temat 2 : - W rzeczywistości udowodnił, że problem jest trudny w APX, ale łatwo jest zweryfikować, że jego redukcje są również ważne dla dowodu twardości NP problemu. - Jego redukcja NIE dotyczy grafów płaskich.

Merrick L. Furst, Jonathan L. Gross i Lyle A. McGeoch, „Finding the maksimum genus embed embed”, Journal of the ACM, t. 35, nr 3, str. 523–534, 1988. 10.1145 / 44483.44485
Rizzi, R .: Trudno znaleźć słabo podstawowe podstawy cyklu. Al Algorytmica 53 (3), 402-424 (2009) 10.1007 / s00453-007-9112-8
László Lovász, „Problem dopasowania matroidów”, w Algebraic Methods in Graph Theory, ser. Colloquia Mathematica Societatis János Bolyai, vol. 25, Szeged, Węgry, 1980, s. 495–517.
Ewald Speckenmeyer, „Untersuchungen zum feedback vertex set problem in ungerichteten grafhen”, praca doktorska, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.

Yixin Cao
źródło

9

Czy istnieje prosty powód, dla którego jest „wyraźnie niepoprawny”?

Suresh Venkat

2

@SureshVenkat Przepraszam za późną odpowiedź: Właśnie zauważyłem to pytanie. Krytyczny błąd znajduje się w Twierdzeniu 4.2, które jest głównym twierdzeniem tego artykułu. Twierdzi się, że otrzymuje pasujące przylegania i parę krawędzi w większym dopasowania przylegania , ale nie w , mogą zwiększać dodając do . Jest to oczywiście błędne, ponieważ definicja dopasowania sąsiedniego wymaga usunięcia wszystkich krawędzi dopasowania sąsiedniego NIE rozłącza wykresu.

M

$M$

{e_{1}, e_{2}}

$\{e_1,e_2\}$

M^{'}

$M'$

M

$M$

M

$M$

{e_{1}, e_{2}}

$\{e_1,e_2\}$

M

$M$

Yixin Cao

ciąg dalszy ... Łatwo można uzyskać pasujące z tylko jedną parą, która spotyka się na wierzchołku , a drugie pasujące dwóch par, z których jedna wykorzystuje incydent z drugą krawędzią do . Para ta nie może być stosowana do zwiększenia . Co więcej, Lemma 4.1 zawiera także błędy krytyczne, ale nie pamiętam szczegółów tego fragmentu. (Wykryłem je na początku 2009 roku i próbowałem natychmiast skontaktować się z autorami, ale niestety nigdy nie otrzymałem żadnej odpowiedzi.)

M

$M$

v

$v$

M^{'}

$M'$

v

$v$

M

$M$

Yixin Cao

9

Odpowiednimi odniesieniami wydają się być:

Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya. W przypadku problemu z niezależnym zestawem niezależnym i problemem związanym ze sprzężeniem zwrotnym dla wykresów bez stopnia wierzchołka przekraczającego trzy. Materiały z pierwszej japońskiej konferencji na temat teorii i zastosowań grafów (Hakone, 1986). Dyskretna matematyka. 72 (1988), no. 1-3, 355–360 .

Li, Deming; Liu, Yanpei. Algorytm wielomianowy do znajdowania zestawu wierzchołków minimalnego sprzężenia zwrotnego 3-regularnego prostego wykresu. Acta Math. Sci. 19 (1999), no. 4, 375–381.

(Ostrzeżenie: nie przeczytałem żadnego, ale oba twierdzą, że rozwiązały problem w czasie wielomianowym. Nie sądzę, żeby różnica między 3-regularnym a maksymalnym stopniem trzecim była istotna dla tego problemu.)

David Eppstein
źródło

Czy problem zestawu wierzchołków sprzężenia zwrotnego można rozwiązać w czasie wielomianowym dla wykresów ograniczonych do 3 stopni?

Odpowiedzi: