Obliczanie stałej Cheegera: możliwe dla jakich klas?

19

Obliczanie stałej Cheegera na wykresie , znanej również jako stała izoperymetryczna (ponieważ jest to zasadniczo minimalny stosunek powierzchni do objętości), jest znana jako NP-zupełna. Ogólnie jest to przybliżone. Chciałbym się dowiedzieć, czy dokładne algorytmy wielomianowe są znane dla specjalnych klas grafów. Na przykład, czy nadal jest kompletny NP dla zwykłych wykresów ? Dla wykresów regularnych odległości ? (Nie badałem istniejących dowodów kompletności NP, aby zbadać ich założenia.) Doceniono wskaźniki literackie - dzięki!

ds.algorithms reference-request graph-algorithms

— Joseph O'Rourke
źródło

3

to miłe pytanie. Czy przybliżenia mają coś wspólnego z najrzadszymi metodami cięcia?

— Suresh Venkat

1

Wiem, że to stare pytanie, ale zastanawiałem się, czy ktoś wiedział o przybliżeniu czasu wielomianu dla ogólnych wykresów, które uzyskują stałą w ramach pewnego ustalonego procentu?

— yberman,

11

Zauważ, że przybliżenie najcięższego cięcia w granicach daje przybliżenie dla zdefiniowanej stałej Cheegera. Oto kilka dokumentów, które podają stałe algorytmy aproksymacyjne dla najrzadszego cięcia na ograniczonych grafach: $\alpha$ $2\alpha$

Rodzaj ograniczony: http://dl.acm.org/citation.cfm?id=1873619
Ograniczona szerokość: http://arxiv.org/abs/1006.3970

Ponadto http://arxiv.org/abs/1006.3970v2 dowodzi, że cięcie rzadkie jest trudne dla NP dla wykresów o szerokości ścieżki 2, i ma całkiem sporo innych odniesień do przybliżania rzadkiego cięcia w ograniczonych przypadkach.

Zakładam, że dla wszystkich klas grafów wymienionych w artykule nie są znane dokładne algorytmy (ponieważ są one zainteresowane przybliżeniami). W szczególności, jeśli najcięższe cięcie jest trudne dla NP dla wykresów o szerokości ścieżki 2, jest również trudne dla NP dla wykresów szerokości 2 i szerokości 2. Przypuszczam, że to nie daje dość dużo miejsca .. może jest jeszcze jeden lepszy parametryzacja dla najrzadszego cięcia.

Jestem całkiem pewien, że najrzadsze cięcie jest trudne dla NP na zwykłych wykresach, ale nie mogę znaleźć odniesienia.

Per zauważył, że nie byłem ostrożny, kiedy spojrzałem na powyższe dokumenty. Wynik twardości dotyczy niejednorodnego cięcia rzadkiego. Obliczanie równomiernego cięcia rzadkiego lub stałej Cheegera jest łatwe na drzewach (WLOG optymalne cięcie oddziela poddrzewo). Przy odrobinie pracy daje dynamiczny algorytm programowania do obliczania stałej Cheegera na ograniczonych wykresach szerokości.

Tabela 1 w powyższym artykule 2 wymienia również wynik, który daje stałe przybliżenie dla wykresów z wykluczonym pomniejszeniem.

$O(\sqrt{\log g})$ $g$

— Sasho Nikolov
źródło

Czy nie można po prostu zrobić regularnego wykresu, dodając pętle własne?

— MCH

2

@MCH tamtędy nieparzyste wierzchołki stopnia pozostanie nieparzysty stopień, a nawet stopień wierzchołki pozostają nawet stopień

— Sasho Nikolov

1

Wspomniany wynik twardości dla ścieżki szerokości 2 dotyczy niejednorodnego cięcia rzadkiego, co nie jest tak istotne dla stałej Cheegera. Rzeczywiście, o ile widzę, obliczenie albo równomiernie rzadkiego cięcia, albo stałej Cheegera dokładnie na wykresach ograniczonej szerokości jest łatwe.

— Per Austrin

5

Aby uzyskać dokładne rozwiązanie na wykresach płaskich, zobacz Park i Phillips, STOC 93 . Odnosi się to zasadniczo do najcięższych wymagań jednolitych, z niewielką różnicą, że ich mianownikiem jest | S | zamiast | S | * | VS |. Jak zauważył Per, przypadek niejednolitych żądań jest inny.

— Robert Krauthgamer
źródło