Existem muitos exemplos em combinatória e ciência da computação em que podemos analisar um problema teórico dos grafos, mas para o análogo do hipergrafo do problema, nossas ferramentas estão faltando. Por que você acha que os problemas geralmente se tornam muito mais difíceis em relação aos hipergrafos trifásicos do que nos gráficos duplos? Quais são as dificuldades de raiz?
Uma questão é que ainda não temos uma compreensão satisfatória da teoria do hipergrafo espectral. Sinta-se à vontade para esclarecer mais essa questão. Mas também estou procurando outros motivos que tornam os hipergráficos objetos mais difíceis.
Respostas:
Nesta questão, entendo que "dificuldade" não se refere a "difícil de calcular", mas a "difícil de estudar".
Os problemas gráficos são mais fáceis (pelo menos para mim) de estudar, já que alguns conceitos são equivalentes. Em outras palavras, se você deseja generalizar as perguntas dos gráficos para as dos hipergráficos, preste atenção à generalização "correta" para que a conseqüência desejada possa ser obtida.
Por exemplo, considere uma árvore. Para gráficos, um gráfico é uma árvore se estiver conectado e não contiver ciclo. Isso é equivalente a estar conectado e ter n-1 arestas (onde n é o número de vértices) e também equivalente a não conter ciclo e ter n-1 arestas. No entanto, para hipergráficos com 3 uniformes, digamos que um hipergrafo com 3 uniformes seja uma árvore se estiver conectado e não contiver ciclo. Mas, isso não é equivalente a estar conectado e ter hipedges n-1, nem conter nenhum ciclo e ter hipedges n-1.
Ouvi dizer que uma das principais dificuldades para provar que o lema da regularidade para hipergrafos uniformes era apresentar as definições corretas de regularidade e conceitos relacionados.
Quando você quiser considerar a "teoria do hipergrafo espectral", pode tentar analisar tensores ou homologia se vir um hipergrafo k-uniforme como um complexo simplimensional (k-1) dimensional, a partir do qual a álgebra linear naturalmente surge. Não sei qual é a generalização "certa" para o seu propósito, ou é possível que nenhuma delas esteja certa.
fonte
Penso que isso se deve em grande parte ao "poder místico das duas coisas" de Lawler (a observação de que muitos problemas parametrizados estão em P para param = 2 e NP-completo para param≥3). Um gráfico é uma coisa que conecta duas tuplas de vértices, e um hipergrafo é uma coisa que conecta uma k-tupla de vértices para k≥3.
Assim, por exemplo, 2-SAT está em P e é essencialmente um problema gráfico, enquanto 3-SAT é um problema em hipergrafos uniformes e é NP-completo.
fonte
Outro motivo seria que temos muito mais conhecimento em relações binárias do que qualquer outra relação n-ária para n maior que 2.
Naturalmente, consideramos relações binárias entre objetos, como adjacência, interseção não vazia, equivalência, etc. Assim, podemos definir gráficos em termos de relações binárias e até definir gráficos com base em alguma relação binária em outro gráfico. (Por exemplo, gráficos de linha, árvores de clique, decomposições de árvores ...)
Mas, como em outras relações n-árias, não temos muita compreensão. Por exemplo, leva algum tempo para surgir uma relação ternária interessante; (Ok, parcialmente devido à minha ignorância) as propriedades são mais fracas e as ferramentas são muito menores no estudo das relações ternárias. (Como definimos relações ternárias simétricas ou transitivas ? Ambas estão entre as relações mais importantes que se pode estudar.)
Mas ainda não sei por que isso acontece entre relações binárias e ternárias. Talvez, como disse o turquistão, essa pergunta seja difícil e possa estar relacionada à compreensão do problema de P / NP.
fonte
Eu ia responder primeiro à pergunta errada: "que exemplo de problemas é muito mais difícil nos hipergráficos do que nos gráficos". Fiquei particularmente impressionado com a diferença ao lidar com o problema de correspondência máxima nos gráficos e o mesmo com os hipergráficos (um conjunto de arestas separadas por pares), que podem modelar com facilidade a coloração, o conjunto independente máximo, o clique máximo ...
Então notei que não era sua pergunta: "quais são as principais dificuldades entre os dois?".
Bem, nesse caso, eu responderia que até agora não vi muitos pontos em comum entre gráficos e hipergrafos. Exceto o próprio nome. E o fato de muitas pessoas estarem tentando "estender" os resultados do primeiro ao outro.
Tive a ocasião de virar as páginas dos "Hypergraphs" de Berge e "Set systems" de Bollobas: eles contêm muitos resultados saborosos, e os que eu achei os mais interessantes tinham pouco a dizer sobre gráficos. Por exemplo, o teorema de Baranyai (há uma boa prova no livro de Jukna).
Eu não os conheço muito, mas estou pensando em um problema de hipergráfico no momento e tudo o que posso dizer é que não sinto nenhum gráfico à espreita em nenhum lugar. Talvez pensemos neles como "difíceis" porque estamos apenas tentando estudá-los com as ferramentas erradas. Não espero que os problemas dos gráficos em que estou trabalhando desapareçam imediatamente usando a teoria dos números (mesmo que às vezes aconteça).
Ah, e mais alguma coisa. Eles são talvez mais difíceis de estudar porque são combinatoriamente muito .... mais ?!
"experimentar todos eles e ver quando funciona" às vezes é uma boa idéia para gráficos, mas com os hipergráficos um rapidamente humilhado pelos números. :-)
fonte