Сложность вычислений самого плотного второстепенного

Рассмотрим следующую проблему.
Вход: неориентированный граф . Вывод: граф H, который является младшим из G с самой высокой граничной плотностью среди всех миноров G , то есть с самым высоким отношением | E ( H ) | / | V ( H ) | ,$G=(V,E)$
$H$$G$$G$$|E(H)|/|V(H)|$

Была ли изучена эта проблема? Это решаемо за полиномиальное время или NP-трудно? Что если мы рассмотрим классы ограниченных графов, такие как классы с исключенными минорами?

Если вместо этого мы попросим самый плотный подграф, то проблема разрешима за полиномиальное время . Если мы добавим дополнительный параметр и запросим самый плотный подграф с k вершинами, задача будет NP-полной (это простое сокращение от k -clique).$k$$k$$k$

Хорошо, поскольку здесь до сих пор нет ответа, позвольте мне сделать хотя бы пару простых замечаний:

Для графов ограниченной ширины дерева должна быть возможность найти наиболее плотный минор (или даже минор с указанным числом ребер и вершин) с помощью обычной сортировки динамической программы на дереве, где каждое состояние динамической программы отслеживает число ребер и вершин в части минора, живущей в поддереве разложения, подмножество вершин в сумке разложения, участвующих в минор, эквивалентности между вершинами в этом подмножестве, вызванные незначительными сокращениями в целом график и уточнение этого отношения эквивалентности, вызванного сокращениями в части несовершеннолетнего, живущего в поддереве.

Если это так, из этого следует, что, когда плотность ниже трех, должна быть возможность найти самый плотный минор за полиномиальное время (с постоянным коэффициентом, который зависит от того, насколько близко к плотности три). Так как графы, у которых самый плотный минор имеет плотность имеют плоские запрещенные миноры и поэтому имеют ограниченную ширину дерева.$\le 3-\epsilon$

Я нашел тесно связанную проблему в статье Bodaender et. и др. , Они считают , что проблема под названием сокращение вырождение, т.е. задача решить для данного графа и K ∈ N , все ли миноры G являются к -degenerate. Теперь плотность ребер по всем подграфам графа и вырождение - это очень похожие понятия (если граф содержит подграф средней степени d, то он также содержит подграф минимальной степени d / 2 ), и я думаю, что их доказательство можно изменить, чтобы показать что проблема поиска самого плотного несовершеннолетнего также NP-полна.$G$$k\in \mathbb{N}$$G$$k$$d$$d/2$

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