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

13

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

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

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

Себастьян Сибертц
источник
6
Моя статья «Плотности семейств минор-замкнутых графов» (Electronic J. Combinatorics 17 (1), Paper R136, 2010, combinatorics.org/Volume_17/Abstracts/v17i1r136.html ) о самых плотных минорах, но в семействах минор-замкнутых графов а не в отдельных графиках. Там вы можете найти что-то подходящее для вашего вопроса.
Дэвид Эппштейн
Это кажется кое-чем связанным со следующим вопросом. Учитывая граф каков размер самого большого минорного клика в G ? Есть ли какие-либо результаты, известные для этого? GG
Чандра Чекури
2
Самый большой минор клики - NP-полный. См. Мою статью «Трудно найти несовершеннолетних из крупных клик», J. Graph Алгоритмы и приложения 13 (2): 197-204, 2009, jgaa.info/accepted/2009/Eppstein2009.13.2.pdf
Дэвид Эппштейн,

Ответы:

7

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

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

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

Дэвид Эппштейн
источник
7

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

kkO(n3)

Себастьян Сибертц
источник