O gráfico de linhas de um hipergrafo é o gráfico (simples) com arestas de pois os vértices com duas arestas de são adjacentes em se tiverem uma interseção não vazia. Um hipergrafo é um hiper-gráfico se cada uma de suas arestas tiver no máximo vértices.G H H G r r
Qual é a complexidade do seguinte problema: Dado um gráfico , existe um hipergrafo tal que é o gráfico de linhas de ?3 H G H
É bem conhecido que o reconhecimento gráficos de linhas de -hypergraph é polinomial, e sabe-se (por Poljak et al., Discrete Appl. Math. 3 (1981) 301-312) que reconhece gráficos de linhas de -hypergraphs é NP -complete para qualquer fixo . r r ≥ 4
Nota: No caso de hypergraphs simples, ou seja, todas as hyperedges são distintas, o problema é NP-completo, conforme comprovado no artigo de Poljak et al.
fonte
Respostas:
Encontrei a versão em diário da pré-impressão de Skums et al. apontado por @mhum; está aqui: Matemática Discreta 309 (2009) 3500–3517 . Lá, os autores corrigiram sua citação da seguinte forma:
A referência 15 é o mencionado Poljak et al. (1981).
Então, eu acho que reconhecer gráficos de linha de hipergrafos (com várias arestas permitidas) é um PROBLEMA ABERTO , e a resposta de @ mhum realmente foi útil nessa descoberta. Obrigado!3
fonte
Eu não tenho acesso ao Poljak et al. artigo, mas o resumo aqui parece indicar que o reconhecimento de gráficos de linha de hiper -gráficos é NP completo para , não . Além disso, a citação nos gráficos de interseção de Edge dos hipergrafos lineares uniformes , Skums et al. (pdf) parece indicar que este é o caso:r ≥ 3 4r r≥3 4
A referência 17 desse trabalho é a citada Poljak et al. (1981). é a classe de hipergrafos uniformes e é a classe de hipergrafos lineares uniformes.L L 3L3 Ll3
fonte