Problem kliki na stałych wykresach

Jak wiemy, funkcja - pobiera ( obejmujący ) z pełnego wykresu -vertex , i wyprowadza iff zawiera klik . Zmienne w tym przypadku odpowiadają krawędzi z . Wiadomo (Razborov, Alon-Boppana), że dla funkcja ta wymaga obwodów monotonicznych o wielkości około . C L I Q U E ( n , k $k$$CLIQUE(n,k)$ n K n 1 G k$G\subseteq K_n$$n$$K_n$$1$$G$$k$ 3 ≤ k ≤ n / 2 n $K_n$$3\leq k\leq n/2$$n^k$

Ale co, jeśli weźmiemy jeden stały wykres i rozważymy monotoniczną funkcję boolowską , która przyjmuje podzbiór wierzchołków i zwraca i kilka wierzchołków w tworząc klika w . Zmienne w tym wypadku odpowiadają wierzchołków o i funkcji jest tylko standardowa funkcja klika lecz ograniczone do , obejmujących subgraphs z jednym stałym wykres . C L I Q U E ( G , k ) S ⊆ [ n ] 1 k S $G\subseteq K_n$$CLIQUE(G,k)$$S\subseteq [n]$$1$$k$$S$$G$$K_n$$G$

1. Czy istnieją -wykresy odwrócone dla których wymaga obwodów monotonicznych o rozmiarze większym niż ? Wydaje mi się że nie. G C L I Q U E ( G , k ) n O ( log n $n$$G$$CLIQUE(G,k)$$n^{O(\log n)}$

2. Czy jest trudnym problemem NP dla niektórych sekwencji grafów ? Wydaje mi się że nie. ( G n : n = 1 , 2 … $CLIQUE(G_n,k)$$(G_n\colon n=1,2\ldots)$

Zauważ, że jeśli są wszystkimi maksymalnymi klikami w , wówczas można obliczyć jako OR funkcji progowej- , której -ta sprawdza, czy . Zatem jeśli , to cały obwód ma wielomian wielkości. Ale co z wykresami z wykładniczą liczbą maksymalnych klików? (Klika jest maksymalna, nie można do niej dodać wierzchołka). G C L I Q U E ( G , k ) r k i | S a ∩ C i | ≥ k r = p o l y ( n $C_1,\ldots,C_r$$G$$CLIQUE(G,k)$$r$$k$$i$$|S_a\cap C_i|\geq k$$r=poly(n)$

Możliwe jest „osadzenie” w dla konkretnego wykresu na wierzchołkach. W szczególności Bollobas i Thomason (1981) wykazali, że jeśli jest wykresem Hadamarda, którego wierzchołki stanowią podzbiory , a dwa wierzchołki i sąsiadują ze sobą iffjest parzyste, wówczas zawiera izomorficzną kopię każdego wykresu na wierzchołkach. Czy fakt ten można połączyć z dolną granicą Razborova (około ) dla aby stwierdzić, że C L I Q U E ( H , k ) H n = 2 $CLIQUE(m,k)$$CLIQUE(H,k)$$H$$n=2^m$[ m ] u v | u ∩ v | H G m m k C L I Q U E ( m , k ) C L I Q U E ( H , k $H$$[m]$$u$$v$$|u\cap v|$$H$$G$$m$$m^k$$CLIQUE(m,k)$$CLIQUE(H,k)$ wymaga obwodów monotonicznych o wielkości około ? Potencjalnym problemem jest to, że chociaż wykres „zawiera” wszystkie wykresy -vertex, wykresy te nie znajdują się na tym samym zestawie wierzchołków. Argument Razborowa wymaga, aby dodatnie i ujemne dane wejściowe ( kliki i uzupełnienia kompletnych stronicowych wykresów) były wykresami na tym samym zbiorze wierzchołków. Ponadto wszystkie dodatnie dane wejściowe ( kliki) są po prostu izomorficznymi kopiami jednej i tej samej stałej kliki.$m^k$$H$ $m$( k - 1 $k$$(k-1)$$k$ $k$

3. Wszelkie pomysły? Czy ktoś widział, że rozważa się tego rodzaju problemy? Mam na myśli problemy decyzyjne dla podgrafów stałego wykresu. Czy powiedzmy, problem SAT dla sub-CNF jednego stałego (zadowalającego) CNF (uzyskanego przez usunięcie niektórych literałów)?

Motywacja: Tego rodzaju problemy związane są ze złożonością kombinatorycznych algorytmów optymalizacji. Ale same wydają się interesujące. Dlaczego powinniśmy szukać algorytmów, które są skuteczne na wszystkich wykresach? W rzeczywistości zazwyczaj interesują nas właściwości małych kawałków jednego (dużego) wykresu (sieci ulic w kraju, facebooka itp.).

Uwaga 1: Jeśli wykres jest dwustronny , to macierz występowania krawędzi wierzchołków nierówności dla wszystkich jest całkowicie niemodularna , i można rozwiązać problem kliki na indukowanych subgrafach za pomocą programowania liniowego. Zatem dla grafów dwustronnych , ma mały obwód (choć nie monotoniczny). x u + x v ≤ 1 ( u , v ) ∉ E G G C L I Q U E ( G , k $G=(L\cup R,E)$$x_u+x_v\leq 1$$(u,v)\not\in E$$G$$G$$CLIQUE(G,k)$

Uwaga 2: Wskazówką, że w przypadku dwustronnych grafów odpowiedź na pytanie 1 „powinna” rzeczywiście być NIE, to że następująca monotoniczna gra Karchmer-Wigderson na potrzebuje tylko bitów komunikacji. Niech będzie największa liczba wierzchołków w pełnym dwustronnego podgrafu z . Alice dostaje zestaw czerwonych węzłów, Bob zestaw niebieskich węzłów, takich jak . Celem jest znalezienie non-krawędź między i .G O ( log n ) k G A B | A | + | B | > k A $G$$G$$O(\log n)$$k$$G$$A$$B$$|A|+|B|>k$$A$$B$

Przeprowadziliśmy badania nad problemem udowodnienia w rozdzielczości drzewiastej, czy ustalony wykres ma klikę o rozmiarze (gdzie jest zwykle małe). W szczególności odkryliśmy, że dla dużej klasy grafów potrzebne są obalenia o rozmiarze .k k n Ω ( k $G$$k$$k$$n^{\Omega(k)}$

Możesz znaleźć artykuł Sparametryzowana złożoność procedur wyszukiwania DPLL pod tym linkiem .

Wierzę, że ten artykuł może odpowiedzieć na twoje pytania: http://arxiv.org/abs/1204.6484

Artykuł definiuje rodziny problemów NP 3SAT, tak że struktura wzoru jest ustalona dla każdego n, a dane wejściowe to polaryzacja wzoru.

Stosując standardową redukcję z 3SAT do CLIQUE (każda klauzula 3CNF definiuje zestaw 8 możliwych przypisań (lub 7 spełniających przypisań), z krawędziami między sprzecznymi przypisaniami), istnieje wykres taki, że po usunięciu jednego wierzchołka dla każdej klauzuli, jest to NP trudno jest znaleźć maksymalną klikę (lub nawet przybliżać jej rozmiar, używając produktów graficznych lub produktów grafu derandomizowanego)

do Q3, istnieją pewne prace empiryczne nad „kręgosłupem” i możliwymi „backdoorami” problemów SAT. kręgosłup to zbiór literałów, które są prawdziwe w każdym zadowalającym zadaniu. Backdoor do problemu SAT to (miejmy nadzieję niewielki) zestaw zmiennych, które zapewniają „skrót” do rozwiązania problemu. te dwie struktury byłyby prawdopodobnie pomocne i / lub kluczowe w zrozumieniu tego, co nazywamy „sub-CNF” lub CNF z usuniętymi niektórymi zmiennymi. ale także DP, algorytm Davis Putnam można postrzegać jako systematyczne badanie wielu „pod-CNF” CNF w celu jego rozwiązania.

[1] Backbones and Backdoors in Satisfiable autorstwa Kilby i in