NP kompletne problemy graficzne na temat właściwości strukturalnych

(To pytanie jest trochę „ankietą”).

Aktualnie pracuję nad problemem, w którym próbuję podzielić krawędzie turnieju na dwa zestawy, z których oba są wymagane do spełnienia niektórych właściwości strukturalnych. Problem „czuje się” bardzo trudne, a ja w pełni się spodziewać, że będzie $\mathcal{NP}$ -complete.For jakiegoś powodu mam problemy ze znalezieniem nawet podobne problemy w literaturze.

Przykład problemu, który uważam za porównywalny do tego, z którym mam do czynienia:

Biorąc pod uwagę ważony turniej , czy istnieje łuk sprzężenia zwrotnego ustawiony w którego krawędzie spełniają nierówność trójkąta? $G = (V,E,w)$ $G$

Zwróć uwagę na różnicę w stosunku do problemu tradycyjnego zestawu sprzężeń zwrotnych: nie dbam o rozmiar zestawu, ale dbam o to, czy sam zestaw ma pewne właściwości strukturalne.

Czy napotkałeś jakieś problemy decyzyjne podobne do tego? Pamiętasz, czy byli oni -Complete lub ? Doceniamy każdą pomoc. $\mathcal{NP}$ $\mathcal{P}$

cc.complexity-theory reference-request np-hardness G. Bach
źródło

Być może możesz wyjaśnić właściwości strukturalne swojego problemu, jest tu wielu ekspertów, którzy znają dowody NPC i zamiast referencji możesz uzyskać dowód NPC :-)

Marzio De Biasi,

@MarzioDeBiasi Bardzo chciałbym uniknąć przedstawienia dowodu na problem, z którym mam do czynienia; po raz pierwszy prowadzę rzeczywiste badania i chciałbym zobaczyć, gdzie mogę dostać się na własną rękę :)

G. Bach,

Dla mnie pytanie brzmi zbyt niejasno i trudno odgadnąć, co naprawdę zostało zadane. Prawdopodobnie pytanie powinno zostać sprecyzowane: co rozumiesz przez „czujesz się podobny do tego” i co rozumiesz przez „łuk sprzężenia zwrotnego ustawiony w G, którego krawędzie spełniają nierówność trójkąta”; czy potrzebujesz odniesienia do problemu dotyczącego zestawu łuków zwrotnych, czy innego problemu?

Yoshio Okamoto,

@YoshioOkamoto Zdaję sobie sprawę, że w tym pytaniu jest pewna dwuznaczność, i miałem nadzieję, że przykład to wyjaśni. Przez „zestaw sprzężenia zwrotnego ustawionego w G, którego krawędzie spełniają nierówność trójkąta” mam na myśli: jeśli

jest zestawem sprzężenia zwrotnego i

, to

F

$F$

(a, b)

$(a,b)$

(b, c)

$(b,c)$

(a, c)

$(a,c)$

\in F

$\in F$

w (a, b) + w (b, c) \geq w (a, c)

$w(a,b) + w(b,c) \ge w(a,c)$ musi przytrzymać, aby

mógł spełnić tę właściwość. Wcześniej tylko kiedykolwiek napotkane problemy w rodzaju

, ale chcę, aby

miał właściwość niezwiązaną z jego licznością.

F

$F$

| F | \leq k

$|F| \le k$

F

$F$

G. Bach,

czy ktoś może podać link / odwołanie do „problemu z tradycyjnym zestawem łukowym”…?

vzn

Odpowiedzi:

Myślę, że istnieje wiele podobnych problemów. Oto dwa w wersji wierzchołkowej i jeden w wersji krawędziowej:

1) Czy dany wykres ma ustawiony niezależny wierzchołek sprzężenia zwrotnego? (nie dbamy o rozmiar zestawu). Ten problem jest NP-zupełny; dowód może pochodzić z dowodu Twierdzenia 2.1 w Garey, Johnson & Stockmeyer .

2) Czy dany wykres ma osłonę wierzchołków, która indukuje drzewo ? (nie dbamy o rozmiar zestawu). Ten artykuł przedstawia NP-kompletność dowodu tego problemu (Twierdzenie 2); nawet dla wykresów dwustronnych.

3) Czy dany wykres ma dominujący zestaw krawędzi, których krawędzie tworzą indukowany nieregularny wykres podrzędny $1$ ? (znane również jako dominujące dopasowanie indukowane lub skuteczne dominowanie krawędzi; wersja wierzchołka jest podana w drugiej odpowiedzi przez Mohammada. Ponownie, nie dbamy o rozmiar zestawu). Ten problem jest NP-zupełny (dobrze znany, po raz pierwszy udowodniony tutaj ), nawet w przypadku płaskich dwustronnych grafów.

$\pi$ $\pi$ $\pi$

vb le
źródło

Właśnie takich problemów szukam!

G. Bach,

@ G.Bach Ponieważ to dokładnie odpowiada na twoje pytanie, proponuję zaakceptować odpowiedź i przyznać nagrodę.

Mohammad Al-Turkistany,

@ MohammadAl-Turkistany Zgadzam się; z jakiegoś powodu będę mógł przyznać nagrodę za godzinę.

G. Bach,

Dzięki za fajny post. Przez dłuższą chwilę myślałem o tych samych liniach.

Mohammad Al-Turkistany,

$C$ $C$ $NP$ $NP$

DW Bange, AE Barkauskas i PJ Slater. Wydajne zestawy dominujące na wykresach . Zastosowania matematyki dyskretnej, Proc. 3rd SIAM Conf., Clemson / South Carolina 1986, 189-199 (1988)., 1988.

Mohammad Al-Turkistany
źródło

Inne warianty zestawu dominującego to połączony zestaw dominujący i niezależny zestaw dominujący .

Radu Curticapean

@RaduCurticapean Ale dzięki tym wariantom zależy Ci na wielkości rozwiązania.

vb le

Tak, przeoczyłem to.

Radu Curticapean

$NP$ $NP$

Dziura to bezcłowy cykl o długości większej niż trzy. Cykl na wykresie ukierunkowanym jest pozbawiony cięciwy, jeśli jego długość jest większa niż 3 i żadne dwa jego wierzchołki nie są połączone krawędzią wykresu skierowanego, która nie należy do cyklu.

$NP$ $P$

$NP$

Znaczenie wykrywania struktury nieparzystej dziury na wykresach podkreśla niedawny przełom twierdzenia Strong Perfect Graph . Pokazuje, że wykres jest idealny wtedy i tylko wtedy, gdy ani on, ani jego wykres uzupełniający nie mają dziwnej dziury.

Mohammad Al-Turkistany
źródło

Cykl jest cyklem indukowanym wtedy i tylko wtedy, gdy jest to cykl bez cięciwy (zwany również otworem).

Mohammad Al-Turkistany,

Obie odpowiedzi brzmią jak problem, którego szukam, dziękuję!

G. Bach,