Determinando o número mínimo de arestas a serem adicionadas para serem conectadas em 3

Diz-se que um gráfico está conectado em se não tiver cortes de vértices (ou seja, pelo menos três vértices devem ser excluídos para desconectar o gráfico). Até onde eu sei, é possível determinar se um gráfico simples é conectado em tempo (exemplo: http://www2.tu-ilmenau.de/combinatorial-optimization/Schmidt2012b.pdf ), mas Eu consideraria útil determinar eficientemente quais arestas adicionar, a fim de tornar nosso gráfico conectado, se ainda não estiver (idealmente, o número mínimo de arestas se isso puder ser feito com eficiência). Alguém conhece esse algoritmo? Nesse caso, eu apreciaria uma referência ou duas. $G$ $3$ $2$ $3$ $O(n)$ $3$

algorithms graph-theory reference-request user340082710
fonte

Respostas:

Para este caso especial de conectividade , ele foi resolvido por Watanabe e Nakamura . O algoritmo é executado no tempo , onde e são o número de vértices e arestas do gráfico de entrada, respectivamente. $3$ $O(n(n+m)^2)$ $n$ $m$

Existe um algoritmo de tempo polinomial para encontrar o número mínimo de arestas a serem adicionadas a um gráfico conectado por para produzir um gráfico conectado a . Veja o capítulo 3 da tese de doutorado de László A. Végh . A tese afirma que não se sabe se a adição de um número mínimo de arestas para produzir um gráfico conectado em geralmente NP-hard. $k-1$ $k$ $k$

Chao Xu
fonte

Se você pode passar de a

k - 1

$k-1$

k

$k$ em tempo polinomial, você pode ir de

0

$0$ para

k

$k$ iterando. Desde a

k

$k$ é limitado por

| V (G) |

$|V(G)|$ , que fornece um algoritmo de tempo polinomial.

David Richerby

Atualizei a resposta após uma leitura mais cuidadosa da tese.

Chao Xu