Complexidade da computação um menor mais denso

13

Considere o seguinte problema.
Entrada: Um gráfico não direcionado . Saída: Um gráfico menor de com a maior densidade de arestas entre todos os menores de , ou seja, com a maior proporção.G=(V,E)
HGG|E(H)|/|V(H)|

Este problema foi estudado? É solucionável em tempo polinomial ou é NP-difícil? E se considerarmos classes de gráfico restritas, como classes com menores excluídos?

Se pedirmos o subgráfico mais denso, o problema é solucionável no tempo polinomial . Se adicionarmos um parâmetro adicional e solicitarmos o subgráfico mais denso com vértices, o problema será NP-completo (essa é uma redução fácil de -clique).kkk

Sebastian Siebertz
fonte
6
Meu artigo "Densidades de famílias de gráficos menores fechados" (Electronic J. Combinatorics 17 (1), Documento R136, 2010, combinatorics.org/Volume_17/Abstracts/v17i1r136.html ) é sobre menores mais densos, mas em famílias com gráficos menores fechados em vez de gráficos individuais. Você pode encontrar algo relevante para sua pergunta lá.
David Eppstein 4/13
Isso parece um pouco relacionado à pergunta a seguir. Dado um gráfico qual é o tamanho da maior clique menor em G ? Existem resultados conhecidos por isso? GG
Chandra Chekuri
2
O maior clique menor é NP-completo. Veja meu artigo "Encontrar grandes menores de clique é difícil", J. Graph Algorithms and Applications 13 (2): 197-204, 2009, jgaa.info/accepted/2009/Eppstein2009.13.2.pdf
David Eppstein

Respostas:

7

Ok, como ainda não há nada aqui no caminho de uma resposta, deixe-me fazer pelo menos algumas observações simples:

Para gráficos de largura de árvore delimitada, deve ser possível encontrar um menor mais denso (ou mesmo um menor com número especificado de arestas e vértices) pelo tipo usual de programa dinâmico na decomposição em árvore, em que cada estado do programa dinâmico acompanha o número de arestas e vértices na parte do menor que vive em uma subárvore da decomposição, o subconjunto de vértices na bolsa da decomposição que participa do menor, as equivalências entre os vértices nesse subconjunto causadas pelas contrações menores no todo gráfico e um refinamento dessa relação de equivalência causada pelas contrações na parte do menor que vive na subárvore.

Nesse caso, seguiria que, quando a densidade estiver abaixo de três, deve ser possível encontrar o menor mais denso no tempo polinomial (com um fator constante que depende de quão próximo de três a densidade está). Pois, os gráficos cujo menor mais denso tem densidade têm menores proibidos planares e, portanto, limitam a largura de árvore.3-ϵ

David Eppstein
fonte
7

GkNGkdd/2

kkO(n3)

Sebastian Siebertz
fonte