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

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!

Zauważ, że przybliżenie najcięższego cięcia w granicach daje przybliżenie 2 α 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$

1. Rodzaj ograniczony: http://dl.acm.org/citation.cfm?id=1873619

2. 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$

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.