Złożoność zliczania wszystkich połączonych podgrafów

Niech G będzie połączonym wykresem.

Jaka jest złożoność zliczania wszystkich połączonych podgrafów, jeśli G jest następujących typów?

• G jest ogólny.
• G jest planarne.
• G jest dwustronny.

Nie dbam o żadne struktury lub ..., po prostu muszę policzyć wszystkie połączone podgrupy! Interesuje mnie również złożoność zliczania wszystkich połączonych podsgrafów z dokładnie k węzłami w G.

Mile widziane są również wskaźniki do dokumentów i książek!

Welsh stwierdza, że ​​problem # P-ukończony nawet w najbardziej ograniczonym przypadku (zliczanie liczby połączonych podgrup płaskiego grafu dwustronnego). Zobacz dół strony 305 w języku walijskim, Dominic (1997), „Approximate Counting”, ankiety w kombinatorykach , Bailey, RA, red., Cambridge University Press, str. 287–324.

W kontekście jednak zastanawiam się, czy on naprawdę ma na myśli połączone rozpinane podgrupy. I to prowadzi mnie do zastanowienia się, którą wersję problemu chcesz: połączonych podsystemów obejmujących, połączonych podgrafów, które nie muszą obejmować, lub połączonych indukcyjnych podsgrafów?

To odpowiedź na odpowiedź Dawida. Nie patrząc na tę książkę, zgaduję, że problemem jest liczenie połączonych podpunktów, ponieważ jest to punkt x = 1 rok = 2 wielomianu Tutte, a autor był tym zainteresowany. Ale tak naprawdę myślę, że te trzy problemy dość łatwo zmniejszają się z liczenia połączonego problemu obejmującego podgraph. Poniższe redukcje powinny działać dla dokładnego zliczania lub przybliżania, choć myślę, że problem z przybliżeniem jest nadal otwarty.

$K_A$$A$ zostanie wybrane wystarczająco duże, typowe połączone wykresy podrzędne wykresu wynikowego odpowiadają N-do-1 połączonym podgraphom obejmującym w G, gdzie N jest łatwe do obliczenia.

$K_A$$A$

$\#P$