Złożoność obliczania najgęstszej nieletniej

13

Rozważ następujący problem.
Dane wejściowe: niekierowany wykres . Dane wyjściowe: wykres który jest niewielką wartością o najwyższej gęstości krawędzi wśród wszystkich nieletnich , tj. O najwyższym stosunku . $G=(V,E)$
$H$ $G$ $G$ $|E(H)|/|V(H)|$

Czy zbadano ten problem? Czy jest to możliwe do rozwiązania w czasie wielomianowym, czy też jest trudne NP? Co się stanie, jeśli weźmiemy pod uwagę klasy z ograniczonymi grafami, takie jak klasy z wykluczonymi małoletnimi?

Jeśli zamiast tego poprosimy o najgęstszy podgraph, problem można rozwiązać w czasie wielomianowym . Jeśli dodamy dodatkowy parametr i poprosimy o najgęstszy podgraph z wierzchołkami, problem jest NP-zupełny (jest to łatwa redukcja z kliki). $k$ $k$ $k$

— Sebastian Siebertz
źródło

6

Mój artykuł „Gęstości mniejszych rodzin zamkniętych grafów” (Electronic J. Combinatorics 17 (1), Paper R136, 2010, combinatorics.org/Volume_17/Abstracts/v17i1r136.html ) dotyczy najgęstszych nieletnich, ale w mniejszych rodzinach zamkniętych grafów zamiast na poszczególnych wykresach. Możesz tam znaleźć coś odpowiedniego do swojego pytania.

— David Eppstein,

To wydaje się trochę związane z następującym pytaniem. Biorąc pod uwagę wykres

jaki jest rozmiar największej kliki mniejszej w

? Czy są na to jakieś wyniki?

G

$G$

G

$G$

— Chandra Chekuri

2

Największa klika mniejsza jest NP-kompletna. Zobacz mój artykuł „Znalezienie dużych małoletnich z kliki jest trudne”, J. Graph Algorytmy i aplikacje 13 (2): 197-204, 2009, jgaa.info/accepted/2009/Eppstein2009.13.2.pdf

— David Eppstein

7

Ok, ponieważ wciąż nie ma tu nic na odpowiedź, pozwól mi przynajmniej poczynić kilka prostych obserwacji:

W przypadku wykresów ograniczonej szerokości powinna istnieć możliwość znalezienia najgęstszego pomniejszenia (lub nawet pomniejszenia z określoną liczbą krawędzi i wierzchołków) za pomocą zwykłego programu dynamicznego w rozkładzie drzewa, w którym każdy stan programu dynamicznego śledzi liczba krawędzi i wierzchołków w części małoletniej mieszkającej w poddrzewie rozkładu, podzbiór wierzchołków w worku dekompozycji, które uczestniczą w drobnej części, równoważność wierzchołków w tym podzbiorze spowodowana niewielkimi skurczami w całości wykres oraz udoskonalenie tej relacji równoważności spowodowanej skurczami części małoletniego mieszkającego w poddrzewie.

$\le 3-\epsilon$

— David Eppstein
źródło

7

$G$ $k\in \mathbb{N}$ $G$ $k$ $d$ $d/2$

$k$ $k$ $O(n^3)$

— Sebastian Siebertz
źródło