Komplexität der Berechnung einer dichtesten Nebenrolle

Betrachten Sie das folgende Problem.
Eingabe: Ein ungerichteter Graph . Ausgabe: Ein Graph H, der ein kleinerer Teil von G mit der höchsten Kantendichte unter allen kleineren Teilen von G ist , dh mit dem höchsten Verhältnis | E ( H ) | / | V ( H ) | .$G=(V,E)$
$H$$G$$G$$|E(H)|/|V(H)|$

Wurde dieses Problem untersucht? Ist es in polynomialer Zeit lösbar oder NP-hart? Was ist, wenn wir eingeschränkte Grafikklassen wie Klassen mit ausgeschlossenen Minderjährigen berücksichtigen?

Wenn wir stattdessen nach dem dichtesten Teilgraphen fragen, ist das Problem in Polynomzeit lösbar . Wenn wir einen zusätzlichen Parameter hinzufügen und nach dem dichtesten Teilgraphen mit k Eckpunkten fragen , ist das Problem NP-vollständig (dies ist eine einfache Reduktion von k- clique).$k$$k$$k$

Ok, da hier noch nichts einer Antwort im Wege steht, lassen Sie mich wenigstens ein paar einfache Bemerkungen machen:

Bei Diagrammen mit begrenzter Baumbreite sollte es möglich sein, durch die übliche Art von dynamischem Programm bei der Baumzerlegung ein dichtestes Moll (oder sogar ein Moll mit einer bestimmten Anzahl von Kanten und Scheitelpunkten) zu finden, wobei jeder Zustand des dynamischen Programms das nachverfolgt Anzahl der Kanten und Scheitelpunkte im Teil des Minderjährigen, der in einem Teilbaum der Zerlegung lebt, die Teilmenge der Scheitelpunkte in der Tasche der Zerlegung, die am Minderjährigen beteiligt sind, die Äquivalenzen zwischen den Scheitelpunkten in dieser Teilmenge, die durch die geringfügigen Kontraktionen im Ganzen verursacht werden und eine Verfeinerung dieser Äquivalenzbeziehung, die durch die Kontraktionen im Teil des im Teilbaum lebenden Minderjährigen verursacht wird.

Wenn dies der Fall ist, sollte es möglich sein, bei einer Dichte unter drei den dichtesten Nebeneffekt in der Polynomzeit zu finden (mit einem konstanten Faktor, der davon abhängt, wie nahe die Dichte bei drei liegt). Denn die Graphen, deren dichtester Nebeneffekt eine Dichte von haben planare verbotene Nebeneffekte und damit eine begrenzte Baumbreite.$\le 3-\epsilon$

Ich habe ein eng verwandtes Problem in einem gefunden Arbeit von Bodaender et. al. . Sie betrachten ein Problem Kontraktion Entartung genannt, das heißt, das Problem für ein bestimmtes Diagramm zu entscheiden , und k ∈ N , ob alle Kinder und Jugendliche von G sind k -degenerate. Die Kantendichte über alle Teilgraphen eines Graphen und die Entartung sind sehr ähnliche Konzepte (wenn ein Graph einen Teilgraphen mit einem Durchschnittsgrad d enthält, dann enthält er auch einen Teilgraphen mit einem Mindestgrad d / 2 ) dass das Problem des Findens eines dichtesten Minderjährigen auch NP-vollständig ist.$G$$k\in \mathbb{N}$$G$$k$$d$$d/2$

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