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,