Um problema de particionamento de arestas em gráficos cúbicos

25

A complexidade do seguinte problema foi estudada?


Entrada : um gráfico cúbico (ou regular) , um limite superior naturalG = ( V , E ) t3G=(V,E)t

Pergunta : existe uma partição de em partes do tamanho tal forma que a soma das ordens dos subgráficos correspondentes (desnecessariamente conectados) seja no máximo ?| E | / 3 3 tE|E|/33t


Trabalho relacionado Encontrei alguns artigos na literatura que provam condições necessárias e / ou suficientes para a existência de uma partição em alguns gráficos contendo três arestas, que são de alguma forma relacionadas, e outras sobre complexidade computacional, questões de problemas que se cruzam com o acima (por exemplo, a partição deve produzir subgráficos isomórficos para ou , e nenhum peso está associado a uma determinada partição), mas nenhum deles lidou exatamente com o problema acima. P 4K1,3P4

Listar todos esses documentos aqui seria um pouco tedioso, mas a maioria deles cita ou é citada por Dor e Tarsi .

20101024: Encontrei este artigo de Goldschmidt et al. , que provam que o problema de particionar arestas em um gráfico em partes contendo no máximo arestas, de modo que a soma das ordens dos subgráficos induzidos seja no máximo , é NP-completo, mesmo quando . É óbvio que o problema permanece NP-completo em gráficos cúbicos, quando exigimos uma igualdade estrita de wrk ?t k = 3 kktk=3k

Informação adicional

Eu tentei algumas estratégias que falharam. Mais precisamente, encontrei alguns contra-exemplos que provam que:

  • maximizar o número de triângulos não leva a uma solução ideal; o que acho de alguma forma contra-intuitivo, uma vez que triângulos são os subgráficos com ordem mais baixa entre todos os gráficos possíveis em três arestas;

  • particionar o gráfico em componentes conectados também não leva necessariamente a uma solução ótima. A razão pela qual parecia promissora pode ser menos óbvia, mas em muitos casos pode-se ver que a troca de arestas para conectar um determinado subgrafo leva a uma solução com peso menor (exemplo: tente isso em um triângulo com uma aresta adicional conectada a cada vértice; o triângulo é uma parte, o resto é uma segunda, com peso total 3 + 6 = 9. Em seguida, trocar duas arestas dá um caminho e uma estrela, com peso total 4 + 4 = 8.)

Anthony Labarre
fonte
Qual é a ordem de um subgráfico?
Mohammad Al-Turkistany
A cardinalidade do seu conjunto de vértices.
Anthony Labarre 19/10/10
1
Talvez olhar para o caso em que o gráfico também é plano possa dar uma ideia do caso mais geral.
Joseph Malkevitch 20/10/10
Obrigado, eu não tinha pensado nisso. Vou tentar e ver se isso ajuda.
Anthony Labarre 21/10
Fiquei imaginando se estratégias como as descritas na seção "informações adicionais" funcionariam ou não. É ótimo que você tenha adicionado essa parte!
Tsuyoshi Ito

Respostas:

3

Aqui está uma sugestão de como mostrar que é NP difícil. Não sei se isso funciona ou não. Primeiro, considere o mesmo problema nas multigráficas. A dureza NP pode ser mais fácil de provar lá. Tente reduzir do MAX CUT cúbico, que é NP difícil de aproximar (Berman e Karpinski "Em alguns resultados mais apertados de inadequação"). Divida cada aresta em duas e, em cada um dos novos vértices de grau 2, anexe um vértice com auto-loop. Sua partição máxima corresponde a um corte máximo?

-

Aqui está um pouco mais de explicação.

(1) O problema de maximizar (número de fontes + número de sumidouros) em todas as orientações de um gráfico cúbico está relacionado ao MAXCUT por alguma função linear. Isso requer mostrar alguma correspondência entre cortes máximos e orientações máximas de fontes e sumidouros. Em uma direção, em um corte máximo (U, V), podemos orientar todas as arestas de U a V. As arestas internas E (U) formam uma correspondência, para que possam ser orientadas arbitrariamente e da mesma forma para E (V), e o número total de fontes e sumidouros é uma função linear do tamanho do corte. Na outra direção, dada uma orientação máxima de fontes e sumidouros, a partição U = vértices de grau 0 ou 1, V = vértices de grau 2 ou 3 fornece um corte.

(2) Na transformação de divisão de arestas que descrevi acima, em uma configuração ideal, cada loop é colorido da mesma forma que a borda próxima a ele e o wlog dessa borda é colorido da mesma forma que a outra borda (sem loop) próxima a aquele. Assim, cada aresta bissetada tem uma cor proveniente do loop anexado e outra cor. Isso corresponde a uma orientação e (1) se aplica.

Colin McQuillan
fonte
Isso é uma ideia. No momento, estou tentando transformar o problema de Goldschmidt et al. No meu, mas vou adicioná-lo à minha lista. Obrigado!
Anthony Labarre 25/10/10