Conectividade de gráficos por remoção de arestas e vértices

17

Digamos que um grafo é -connected se a remoção de qualquer vértices e qualquer arestas de folhas sempre um grafo conexo. Por exemplo, um gráfico conectado a , de acordo com a definição padrão, é conectado , de acordo com a nova definição. Existe um algoritmo de tempo polinomial para decidir se está (a, b) conectado? Aqui considero que a entrada é G , a e b .( a , b ) a b G k ( k - 1 , 0 ) G ( a , b ) G a bG(uma,b)umabGk(k-1 1,0 0)G(uma,b)Gumab

alguém
fonte
11
Problema de lição de casa?
Chandra Chekuri
6
Eu vim a esta pergunta durante uma conversa de Janez Zerovnik sobre conectividade de redes cerca de 2/3 anos. Para ser sincero, não me lembro dos detalhes. Desde então, perguntei a cerca de 4 pesquisadores e ninguém viu como reduzi-lo à conectividade de vértices (ou conectividade de borda), que seria a abordagem óbvia. Além disso, ninguém poderia apontar um teorema do tipo Menger. Então, sim, acho que essa é uma questão de nível de pesquisa, possivelmente com uma resposta simples ou não.
alguem
7
Não sei por que as pessoas às vezes assumem que uma pergunta é um dever de casa sem pensar primeiro. Eu acho que você não deve declarar algo como lição de casa, a menos que você saiba como resolvê-lo.
Domotorp
11
@domotorp: as pessoas geralmente estão perguntando se é um dever de casa, não reivindicando. É difícil julgar se uma pergunta está no nível da lição de casa ou não quando a pergunta não contém antecedentes / motivação.
Kaveh
2
Entendo que minha pergunta possa ser mal interpretada como lição de casa por vários motivos, mas agora devemos seguir em frente. Na verdade, com o comentário de Chandra Chekuri eu tenho alguma esperança de que talvez a questão pode ter uma resposta simples ...
alguém

Respostas:

8

Esta é uma versão editada de uma "resposta" anterior que reivindicou incorretamente um algoritmo de tempo polinomial para o problema. O que escrevo abaixo é uma conexão com um problema existente, o que sugere que o problema é difícil.

Deixe- ser dois nós em G e queremos verificar se eles estão ( a , b ) -connected. Essa é a remoção de qualquer um de nós e nenhum b bordas não deve desconectar s e t . Outra maneira de analisar o problema da seguinte forma: qual é o número mínimo de nós que precisamos remover para reduzir a conectividade de borda entre s e t para bs,tG(uma,b)umabststb? Esses tipos de problemas foram estudados sob o nome de cortes de várias rotas e são fluxos duplos para várias rotas. Vários resultados de aproximação foram mostrados, embora muitos problemas básicos ainda não tenham sido resolvidos. Um resultado de interesse é o seguinte. Suponhamos que cada aresta tem um custo e que pretende remover o conjunto de custo mínimo das bordas para reduzir a borda-conectividade entre s e t a b ; então esse problema é NP-Hard quando b faz parte da entrada. Este resultado está no artigo de Barman e Chawla: http://arxiv.org/abs/0908.0350c(e)stbb

Dois artigos que aparecerão no próximo SODA 2012 estão em cortes de várias rotas que têm mais resultados sobre o assunto. O de Chuzhoy etal apresenta resultados de dureza para algumas variantes.

Chandra Chekuri
fonte
O artigo sobre Chuzhoy etal já está disponível no ArXiv: arxiv.org/abs/1112.3611
Chandra Chekuri