Reconhecendo gráficos de linha de hipergrafos

20

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 rHGHHGrr

Qual é a complexidade do seguinte problema: Dado um gráfico , existe um hipergrafo tal que é o gráfico de linhas de ?3 H G HG3HGH

É 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 42rr4

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.

user13136
fonte
Vale a pena esclarecer que você permite arestas repetidas em um hipergrafo.
András Salamon
@ Salamon: Obrigado pela sugestão, eu editei em conformidade. Sinto muito, mas aprendi que, por definição, os hipergrafos podem ter várias arestas!
precisa saber é o seguinte

Respostas:

8

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 situação muda radicalmente se alguém pegar vez de . Lovasz colocou o problema de caracterizar a classe e observou que ela não possui caracterização por uma lista finita de subgráficos induzidos proibidos ( uma caracterização finita ) [9]. Foi provado que os problemas de reconhecimento " " para " " [15], " " para e o problema de reconhecimento de gráficos de interseção de arestas de - hipergrafos uniformes sem arestas múltiplas [15] são NP-completos.k = 2 L 3 G L k k 4 G L l 3 k 3 3k3k=2L3GLkk4GL3lk33

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

vb le
fonte
Que bom saber! Obrigado pelo seu tempo.
precisa saber é o seguinte
8

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 4rr34

A situação muda principalmente se considerarmos vez de . Lovasz colocou o problema de caracterizar a classe e observou que ela não possui caracterização por uma lista finita de subgráficos induzidos proibidos ( uma caracterização finita ) [10]. Foi provado que os problemas de reconhecimento " " [17] e " " para [5] estão completos em NP.k = 2 L 3 G L 3 G L l k k 3k=3k=2L3GL3GLklk3

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 3L3L3l

mhum
fonte
5
O artigo Poljak et al. (1981) prova o seguinte caso especial (Teorema 2.2): Reconhecer se um gráfico é o gráfico de linhas de um hiper- gráfico com todas as hiperedges distintas é NP-completo. A citação de Skums et al. parece estar incorreto. 3
precisa saber é o seguinte
Ah Entendo. Nem sempre é claro para mim se o termo "hipergrafo" inclui hipermultigráficos (multi-hipergráficos?).
Mhum
Obrigado pela resposta e desculpe pela minha formulação solta.
precisa saber é o seguinte
@vb le obrigado por vincular e investir na minha pergunta!
precisa saber é o seguinte
5
@ user13136: De nada! Isso ocorre porque conheço pessoas, inclusive eu, que acreditam que o problema deve ser NP-completo, mas não consegue encontrar uma referência / prova.
vb le