Czy Cheeger jest stały -trwały?

Przeczytałem w niezliczonych artykułach, że wyznaczanie stałej Cheegera na wykresie to -hard. To wydaje się być twierdzeniem ludowym, ale nigdy nie znalazłem ani cytatu, ani dowodu na to stwierdzenie. Komu mam to przypisać? W starym artykule (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar potwierdza to twierdzenie „dla wykresów o wielu krawędziach”. $\mathsf{NP}$

reference-request graph-theory spectral-graph-theory

— Delio M.
źródło

Odpowiedzi:

Ja również napotkałem ten problem, gdy pisałem artykuł, który wymagał cytowania twardości rozszerzania krawędzi (lub stałej Cheegera) zdefiniowanej jako. Klasyczny artykuł Leightona i Rao na temat separatorów ( http://dl.acm.org/citation.cfm?id=331526 ) wspomina, że jest to trudny problem i odnosi się do artykułu Garey, Johnsona i Stockmeyera ( http: / /www.sciencedirect.com/science/article/pii/0304397576900591 $\min_{S \subset V, |S| \leq |V|/2} |\delta(S)|/|S|$ ). Przez chwilę nie mogłem rozgryźć, do czego się odnoszą, ponieważ nie ma wzmianki o rozszerzeniu krawędzi we wspomnianym artykule. Skomunikowałem o tym z Avi Wigdersonem. W końcu okazało się, że można użyć twardości Max-Cut, jak pokazano w pracy Garey i in., Aby stosunkowo łatwo pokazać, że ekspansja krawędzi jest trudna. Teraz zapominam o szczegółach, ale odtworzenie nie powinno być trudne. Artykuł Blum etal o twardości sprawdzania, czy wykres jest superkoncentratorem, nie implikuje bezpośrednio twardości rozszerzania się krawędzi. Nie są technicznie tym samym problemem.

— Chandra Chekuri
źródło

Mój artykuł, który używa twardości rozszerzania krawędzi, znajduje się poniżej onlinelibrary.wiley.com/doi/10.1002/net.20165/abstract . Odnosimy się do pracy Leighton-Rao i Garey, Johnson, Stockmeyer o twardości rozszerzania krawędzi.

— Chandra Chekuri,

Dzięki! Więc technicznie rzecz biorąc, twardość wyznaczania stałej Cheegera nie jest potwierdzona w literaturze?

— Delio M.

@DelioM. odniesienie do Kaibela w jednej z odpowiedzi Mohammada ma kompletny dowód. Jest to po prostu redukcja Garey-Johnson-Stockmeyer od nieważonego maksymalnego cięcia do bisekcji min, z krótkim dowodem, że na wykresach uzyskanych przez redukcję najrzadsze cięcie jest bisekcją.

— Sasho Nikolov,

Chociaż muszę wyznać, że się zgubiłem. Zawsze myślałem, że maksymalne cięcie wiąże się z kwestią charakteryzowania „jak dwustronny” jest wykres. Jak może to pomóc znaleźć „jak połączony” jest wykres? Z drugiej strony, w jaki sposób druga najniższa wartość własna bezsensownego Laplaciana może wiązać się z drugą najniższą wartością własną dla laplacian? Że dolna granica jest oczywista, ale górna granica?

— Delio M.

@DelioM. Maksymalne cięcie jest najpierw redukowane do bisekcji minimalnej przez dodanie większej liczby wierzchołków i przyjęcie uzupełnienia wynikowego wykresu. Ta redukcja odnosi się zatem do tego, jak bliski jest dwustronny jeden wykres do tego, jak połączony jest inny wykres (związany z dopełnieniem pierwszego).

n

$n$

— Sasho Nikolov,

Rzeczywisty dowód twardości obliczania stałej Cheegera (lub rozszerzenia krawędzi) podał Kaibel w raporcie technicznym poprzez redukcję problemu MAX Cut (patrz twierdzenie 2). Dowód jest rozszerzeniem dowodu na twardość problemu równości podanego przez Garey, Johnson i Stockmeyer w niektórych uproszczonych problemach z NP-kompletnym wykresem . $NP$ $NP$

V. Kaibel: O ekspansji wykresów 0/1-polytopów. Raport techniczny arXiv: math.CO/0112146, 2001

EDYCJA : Poniższy argument jest niepoprawny , jak zauważył Chekuri, i pozostawiony w celach edukacyjnych.

Nie jest to odniesienie, o które prosiłeś, ale wyjaśnia status folkloru wyniku twardości.

Oto dowód na kompletność CoNP przy podejmowaniu decyzji, czy podłączony wykres sześcienny jest ekspanderem krawędzi, a zatem ustalenie stałej Cheegera jest trudne dla CoNP. $h(G)$

Problemem minimum równego podziału jest -Complete $NP$ podłączonych wykresy sześciennych. W tym miejscu chcemy zdecydować, czy wykres z liczbą całkowitą można podzielić na dwie równe części, tak że liczba przyciętych krawędzi jest mniejsza niż . $G$ $k$ $k$

Zauważ, że uzupełnienie tego problemu jest równoważne z podjęciem decyzji, czy wykres jest ekspanderem, czy nie (każda zbalansowana partycja ma przycięte krawędzie więcej niż ). $G$ $V$ $k$

PS Arora w seminarium stwierdza, że jest to -hard rozpoznać -expander wykresu (krawędź rozprężeniu). http://www.cs.princeton.edu/~zdvir/apx11slides/arora-slides.pptx $CoNP$ $\alpha$

— Mohammad Al-Turkistany
źródło

Ten dowód również nie działa, ponieważ rozmiar bisekcji min nie mówi sam o rozszerzeniu krawędzi. Na przykład odłączony wykres na wierzchołkach może mieć minimalną bisekcję .

2 n

$2n$

(n - 2)^{2}

$(n-2)^2$

— Sasho Nikolov,

Wykres jest połączonym wykresem sześciennym i dla tej klasy problem minimalnej przecięcia jest NP-zupełny.

G

$G$

— Mohammad Al-Turkistany

@SashoNikolov Nigdy nie widziałem nikogo zainteresowanego ekspansją odłączonych wykresów.

— Mohammad Al-Turkistany,

Arora, nie Aurora. Nie wątpię, że podjęcie decyzji o jest trudne. Ale w dwóch odpowiedziach nie podałeś ani referencji z dowodem, ani dowodu. Odłączone wykresy mają jedynie pokazać, że twoje argumenty są fałszywe. Twoja „poprawka” też nie działa. Mogę z łatwością pokazać ci połączony wykres sześcienny z dużym minimalnym przecięciem i stałą Cheegera dowolnie bliską zera. Te dwa problemy są powiązane, ale nie w trywialny sposób, który sugerujesz.

h (G) \geq α

$h(G) \geq \alpha$

— Sasho Nikolov,

@ MohammadAl-Turkistany: weź dwa połączone wykresy sześcienne bez mostków, które są ekspanderami, jeden z 2n wierzchołkami, a drugi z n wierzchołkami i połącz je z trzema krawędziami, dodając około 3 nowych wierzchołków z każdej strony poprzez podzielenie 3 krawędzi. Teraz minimalizacja będzie duża ( ), ponieważ musisz odciąć sporą część większego ekspandera, ale rozszerzenie jest niewielkie, ponieważ możesz podzielić dwa ekspandery, przecinając tylko 3 krawędzie.

Ω (n)

$\Omega(n)$

— Chandra Chekuri,