NP-pełna właściwość graficzna, która jest dziedziczna, ale nie addytywna?

Właściwość wykresu jest nazywana dziedziczną, jeśli zostanie zamknięta w odniesieniu do usuwania wierzchołków (tj. Wszystkie indukowane podgrupy dziedziczą właściwość). Właściwość graf nazywa się addytywną, jeśli jest zamknięta w odniesieniu do przyjmowania rozłącznych związków.

Nie jest trudno znaleźć właściwości dziedziczne, ale nie addytywne. Dwa proste przykłady:

$\;\;\;$ (1) Wykres jest kompletny.

$\;\;\;$ (2) Wykres nie zawiera dwóch cykli rozłącznych wierzchołków.

W takich przypadkach jest oczywiste, że właściwość jest dziedziczona przez indukowane wykresy podrzędne, ale biorąc pod uwagę dwa rozłączne wykresy, które mają właściwość, ich związek może tego nie zachować.

Oba powyższe przykłady są rozstrzygającymi właściwościami czasu (chociaż dla (2) jest to nieco mniej banalne). Jeśli chcemy twardszych właściwości, można je nadal tworzyć zgodnie ze wzorem (2), ale zastępując cykle bardziej skomplikowanymi typami wykresów. Wtedy jednak możemy łatwo natknąć się na sytuację, w której problem nawet nie występuje w , przy standardowych założeniach złożoności, takich jak . Znalezienie przykładu, który mieści się w , wydaje się mniej trywialne , ale wciąż jest trudne. $NP$ $NP\neq coNP$ $NP$

Pytanie: Czy znasz (najlepiej naturalną) właściwość wykresu pełnego która jest dziedziczna, ale nie addytywna? $NP$

cc.complexity-theory graph-theory graph-algorithms np Andras Farago
źródło

Zadałeś teraz szereg pytań na temat „naturalnych” właściwości. Pomocne może być zrozumienie motywacji niektórych z tych pytań.

Suresh Venkat

@Suresh Chciałbym lepiej zrozumieć, co sprawia, że problem jest naturalny, a nie sztuczny. Myślę, że koncepcja naturalności jest ważnym pomostem między teorią a rzeczywistością i warto ją zbadać. Intrygujące jest dla mnie to, że chociaż nie mamy formalnej definicji tego, które problemy są „naturalne”, ludzie zwykle mają wyraźną zgodność co do tego, czy dany problem jest naturalny, czy nie. Być może opublikuję osobne pytanie dotyczące tego problemu, aby dowiedzieć się więcej o tym, jak inni go postrzegają.

Andras Farago

Odpowiedzi:

Myślę, że problem pokrycia kliki, który pyta, czy istnieje podział wierzchołków w zestawach tak, że każdy zbiór powoduje klik, ma pożądane właściwości. $k$ $k$

Oczywiste jest, że pobranie indukowanych wykresów podrzędnych nie może zwiększyć minimalnego rozmiaru takiej partycji. Z drugiej strony, jeśli weźmiesz rozłączne połączenie dwóch wykresów, musisz wziąć połączenie podziału w kliki każdego z nich.

Vinicius dos Santos
źródło

Podobnie osłona wierzchołka / dominujący zestaw wielkości co najwyżej działa podobnie.

k

$k$

Ale oba wymienione przez ciebie problemy są wielomianowe dla ustalonego , prawda? Myślę, że jeśli zmusisz do bycia częścią danych wejściowych, przestanie to być dobrze zdefiniowana właściwość w sensie zadanego pytania.

k

$k$

k

$k$

Vinicius dos Santos

-clique nieruchomość okładka, jak stwierdzono w odpowiedzi, nie jest . Wykres może mieć podział na kliki, ale jego podrozdział może nie dziedziczyć tej właściwości. Dotyczy to zarówno stałej, jak i zmiennej .

k

$k$

h e r e d i t a r y

$hereditary$

k

$k$

k

$k$

Andras Farago

Można to łatwo rozwiązać, pozwalając na puste partycje (jeśli pierwotny problem na to nie pozwala, rozważ tę zmodyfikowaną wersję). Zamiast „kliki w rozmiarze ” rozważ „rozmiar co najwyżej ”.

k

$k$

k

$k$

Vinicius dos Santos

Tak, myślę, że dzięki tej modyfikacji jest to teraz poprawna odpowiedź! Jeśli naprawimy , wówczas właściwość jest równoważna do „czy uzupełnienie G 3 można pokolorować?” (co oznacza, że dopełnienie można pokolorować maksymalnie o 3 kolory). Jest to dziedziczne i rzeczywiście kompletne NP, ze względu na znaną kompletność NP wykresu 3-kolorowności. Obiekt jest również zakaz dodatek, bo jeśli i zarówno indywidualnie mieć ich uzupełnienia 3-colorable, nadal dopełnieniem ich związku rozłącznych nie może pozostać 3-colorable (może to wymagać aż 6 kolorów).

k = 3

$k=3$

G_{1}

$G_1$

G_{2}

$G_2$

Andras Farago

Rozważ ten problem

Biorąc pod uwagę wykres decydujący, czy jego zestaw wierzchołków można podzielić na dwa zestawy rozłączne, tak że indukowane wykresy tworzone przez szwy wykazują właściwości i , są NP-kompletne . $G$ $P$ $Q$

Pozostaje NP kompletny, nawet jeśli właściwości są dziedziczne.

Oczywiste jest, że rozwiązanie powyższego problemu dla wykresu zapewnia również rozwiązanie dla indukowanych subgrafów. Ale po połączeniu wykresów z tej samej rodziny co G może nie zostać rozwiązanych za pomocą tego rozwiązania.

Na przykład dzielenie ogólnych wykresów na rozłączne wykresy przedziałów jednostkowych jest NP całkowite, ale po zsumowaniu wszystkich możliwych krawędzi (uzupełnieniu wykresu) rozwiązuje problem w trywialny sposób.

Dibijaj
źródło

Należy pamiętać, że pytanie szuka właściwości, która nie jest addytywna. W twoim przykładzie nic nie wydaje się gwarantować, że muszą istnieć dwa wykresy, które oba mają właściwość, ale ich rozłączny związek nie ma.

Andras Farago,

Określić liczbę pokrywy cykl grafu , jako minimalna liczba cykli takie, że (i) każdy wykres stopnia na podgrupie , (ii) każdy krawędź jest obecne w niektórych . Przypuszczam, że: $G = (V,E)$ $C_1,\ldots,C_m$ $C_i$ $V$ $E$ $C_i$

(1) dla , NP jest kompletne, aby zdecydować, czy ma najwyżej numer pokrycia cyklu , $k \geq 3$ $G$ $k$

$k = 2$

Jeśli (1) jest prawdą, powinien odpowiedzieć na twoje pytanie, ponieważ daje właściwość dziedziczną, ale wyraźnie nieaddytywną.

(UWAGA DODANA: hipoteza (2) różni się od „hipotezy o podwójnym cyklu okładki” Szekeresa i Seymour, pomimo homonimiczności).

Super8
źródło

Ta właściwość nie jest dziedziczna. Usunięcie wierzchołka może zwiększyć potrzebną liczbę cykli do pokrycia wszystkich krawędzi, ponieważ usunięty wierzchołek może wyeliminować cykl, który został użyty do pokrycia wielu krawędzi. Najprostszym przykładem jest sytuacja, gdy cały wykres jest tylko cyklem. Usunięcie wierzchołka uniemożliwia dowolne pokrycie cyklu, ponieważ nie pozostały żadne cykle.

Andras Farago

G

$G$

G

$G$

v

$v$

v

$v$

k

$k$