Zależność między trudnością rozpoznawania klasy grafowej a zakazaną charakterystyką subgrafu

22

Rozważam klasy grafów, które można scharakteryzować za pomocą zabronionych subgrafów.

Jeśli klasa grafów ma skończony zestaw zabronionych podgraphów, wówczas istnieje trywialny algorytm wielomianowego rozpoznawania czasu (można po prostu użyć brutalnej siły). Ale nieskończona rodzina zakazanych subgraphów nie oznacza twardości: istnieją pewne klasy z nieskończoną listą zakazanych subgrafów, tak że rozpoznanie może być również przetestowane w czasie wielomianowym. Wykresy Chordal i Perfect są przykładami, ale w takich przypadkach istnieje „ładna” struktura zakazanej rodziny.

Czy istnieje znany związek między trudnością uznania klasy a „złym zachowaniem” zakazanej rodziny? Taka relacja powinna istnieć? To „złe zachowanie” zostało gdzieś sformalizowane?

cc.complexity-theory graph-theory np-hardness Vinicius dos Santos
źródło

Odpowiedzi:

31

Chociaż intuicyjne wydaje się to, że lista zabronionych (indukowanych) subgrafów dla klasy grafów z rozpoznawaniem trudnym dla NP powinna posiadać pewną „wewnętrzną” złożoność, ostatnio znalazłem w literaturze kilka uderzających negatywnych dowodów na tę intuicję.C

Być może najprostszy do opisania jest następujący, zaczerpnięty z artykułu B. Lévêque, D. Lin, F. Maffray i N. Trotignon .

Niech będzie rodziną grafów, które składają się z cyklu o długości co najmniej czterech plus trzy wierzchołki: dwa przylegające do tego samego wierzchołka u cyklu i jedno przylegające do wierzchołka v cyklu, gdzie u i v są nie kolejne w cyklu (i żadnych innych krawędzi).Fuvuv

Teraz niech będzie rodziną wykresów, które składają się dokładnie w ten sam sposób, chyba że dodasz cztery wierzchołki: dwie przylegające do samego wierzchołka u cyklu (jak poprzednio), ale teraz dwa przylegające do samego wierzchołka v z cykl, w którym ponownie u i v nie są następujące po sobie.fa′uvuv

Zatem klasa grafów, w których jest zabronionym indukowanym podgraphem, ma rozpoznawanie w czasie wielomianowym, podczas gdy rozpoznanie klasy, która ma F ' jako zabronione indukowane podgrupy jest NP-trudne.fafa′

Dlatego trudno mi wyobrazić sobie jakiś ogólny warunek, który musi spełnić lista zabronionych indukowanych subgrafów, gdy wynikiem jest klasa z trudnym rozpoznaniem (NP-), biorąc pod uwagę, że taki warunek będzie musiał oddzielić „bardzo podobny” i F ′ powyżej.fafa′

Hugo Nobrega
źródło
2
Ładna odpowiedź - to dość delikatne.
Suresh Venkat
Ciekawy. Czy jest jakaś szansa, że ​​miałoby to coś wspólnego z wyrazistością logiki wymaganej do opisania wzoru? Myślę o czymś takim, jak w przypadku języków formalnych, w których złożoność języka można w równoważny sposób scharakteryzować poprzez sposób jego zdefiniowania (regexp, gramatyka formalna ...) lub maszynę wymaganą do jego rozpoznania (automat, pushdown ...) lub ekspresyjność logiki wymaganej do napisania formuły charakteryzującej słowa danego języka (na przykład MSO dla zwykłych języków).
a3nm
3
To ciekawy pomysł, ale znowu nie mogę przestać myśleć, że i F ' są tak blisko, że trudno sobie wyobrazić sposób ich „rozdzielenia” w ten sposób (powiedzmy, że F można opisać w języku, w którym F ' nie jest ). Mógłbym być po prostu zbyt negatywny ...! Przyznaję, że chodzę tutaj na „intuicję”, więc chętnie się dowiem, że się mylę. fafa′fafa′
Hugo Nobrega,
@ Hugo: jedną namacalną różnicą między nimi jest symetria w charakterystyce - z natury nie ma możliwości rozróżnienia wierzchołków u i v . Co się stanie, jeśli weźmie się pod uwagę rodzinę F 0 cykli długości co najmniej czterech plus dwa dodatkowe wierzchołki sąsiadujące z nieciągłymi wierzchołkami w cyklu? Czy przywrócenie symetrii w kierunku „innym” (usunięcie wierzchołka z F zamiast dodania jednego) utrudnia to ponownie? fa′uvfa0fa
Steven Stadnicki
@Steven: Chyba nie, można wykryć wykresy w , losowo zgadując 8 węzłów, tworząc obie strony wykresu, i wykonać algorytm trzy w drzewie na trzech węzłach, podobnie jak w Twierdzeniu 3.1. Daje to algorytm czasu wielomianowego do wykrywania F 0 . fa0fa0
Hsien-Chih Chang 張顯 之
5

Odpowiedź @ Hugo jest naprawdę miła i tutaj chcę dodać kilka osobistych opinii.

Istnieją pokrewne rodziny podobne do wykresów w rodzinie F i F '. Wykresy w rodzinie B1 w artykule są zwykle nazywane piramidami. A wykresy w rodzinie B2 są zwykle nazywane pryzmatami. Zobacz odpowiedź tutaj, aby zobaczyć ilustrację. W literaturze dotyczącej problemów z indukowanym wykrywaniem subgrafu zastosowano je do wykrywania dziur parzystych / nieparzystych, które są cyklami akordowymi o długości parzystej / nieparzystej. Według znanego twierdzenia o silnym idealnym grafie, wykres G jest idealny, jeśli zarówno G, jak i dopełnienie G nie zawierają nieparzystych otworów.

W przypadku rodzin piramid i pryzmatów faktycznie istnieją między nimi różnice - jedno ma indukowane poddrzewo z trzech liści, a drugie nie. Nazywa się to problemem „trzech na drzewie” , który badali Chudnovsky i Seymour. Zaskakujące jest to, że ustalenie, czy istnieje indukowane drzewo, które zawiera trzy podane węzły, jest wykonalne, podczas gdy problem „drzewa czterech na środku” jest trudny NP . (Wyśrodkowane drzewo jest drzewem o najwyżej jednym węźle o stopniu większym niż 2.) Różnice między F i F 'wydają się być spowodowane z tego samego powodu.

Wydaje się jednak, że pełna charakterystyka jest wciąż trudna, ponieważ nawet nie znamy złożoności wykrywania wykresów w niektórych rodzinach, które wyglądają dość prosto, jak na przykład wykresy nieparzyste dołkowe (!). A dla rodzin, które znamy, istnieje algorytm wielomianowy, taki jak doskonałe wykresy i wykresy bez dziur, chociaż istnieją ogólne strategie (oparte na rozkładach) projektowania algorytmu, należy podać konkretne twierdzenie strukturalne dla im. Zazwyczaj jest to proces zależny od rodziny i przez większość czasu dowody są naprawdę długie. ( Oto przykład wykresu bez dziur, w którym papier ma ponad 90 stron.)

Byłoby jednak interesujące mieć pewne klasyfikacje pod kątem problemów z wykrywaniem subgrafu, w sensie podobnym do problemu trzech na drzewie.

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