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

Rozważ następujący problem.
Dane wejściowe: niekierowany wykres . Dane wyjściowe: wykres H, który jest niewielką wartością G, o najwyższej gęstości krawędzi wśród wszystkich nieletnich G , tj. O najwyższym stosunku | E ( H ) | / | V ( H ) | .$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 k wierzchołkami, problem jest NP-zupełny (jest to łatwa redukcja z k- kliki).$k$$k$$k$

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$

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

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