Complejidad de la computación de un menor denso

13

Considere el siguiente problema.
Entrada: Un gráfico no dirigido . Salida: Un gráfico H que es un menor de con la densidad de borde más alta entre todos los menores de , es decir, con la relación más alta.G=(V,E)
HGG|E(H)|/|V(H)|

¿Se ha estudiado este problema? ¿Es solucionable en tiempo polinómico o es NP-duro? ¿Qué sucede si consideramos clases de gráficos restringidas como clases con menores excluidos?

Si solicitamos el subgrafo más denso en su lugar, el problema se puede resolver en tiempo polinómico . Si agregamos un parámetro adicional y solicitamos el subgrafo más denso con vértices, el problema es NP-completo (esta es una reducción fácil de -clique).kkk

Sebastian Siebertz
fuente
66
Mi trabajo "Densidades de familias de gráficos cerrados menores" (Electronic J. Combinatorics 17 (1), Paper R136, 2010, combinatorics.org/Volume_17/Abstracts/v17i1r136.html ) trata sobre menores más densos, pero en familias de gráficos cerrados menores en lugar de en gráficos individuales. Puede encontrar algo relevante para su pregunta allí.
David Eppstein
Esto parece algo relacionado con la siguiente pregunta. Dado un gráfico ¿cuál es el tamaño de la mayor camarilla menor en G ? ¿Hay algún resultado para saberlo? GG
Chandra Chekuri
2
La camarilla más grande es NP-completa. Vea mi artículo "Encontrar una gran camarilla de menores es difícil", J. Graph Algorithms and Applications 13 (2): 197-204, 2009, jgaa.info/accepted/2009/Eppstein2009.13.2.pdf
David Eppstein

Respuestas:

7

Ok, como todavía no hay nada aquí en el camino de una respuesta, permítanme al menos hacer un par de observaciones simples:

Para los gráficos de ancho de árbol limitado, debería ser posible encontrar un menor más denso (o incluso un menor con un número específico de aristas y vértices) mediante el tipo de programa dinámico habitual en la descomposición del árbol, donde cada estado del programa dinámico realiza un seguimiento de la número de aristas y vértices en la parte del menor que vive en un subárbol de la descomposición, el subconjunto de vértices en la bolsa de la descomposición que participa en el menor, las equivalencias entre vértices en este subconjunto causadas por las contracciones menores en el conjunto gráfico, y un refinamiento de esta relación de equivalencia causada por las contracciones en la parte del menor que vive en el subárbol.

Si es así, se seguiría que, cuando la densidad es inferior a tres, debería ser posible encontrar el menor más denso en tiempo polinómico (con un factor constante que depende de qué tan cerca de tres sea la densidad). Para, las gráficas cuyo menor más denso tiene densidad tienen menores prohibidos planos y, por lo tanto, delimitan el ancho del árbol.3ϵ

David Eppstein
fuente
7

GkNGkdd/2

kkO(n3)

Sebastian Siebertz
fuente