Connectivité des graphiques par suppression des arêtes et des sommets

Disons qu'un graphe est ( a , b ) -connexe si la suppression de tout un des sommets et des b arêtes de G feuilles toujours un graphe connexe. Par exemple, un graphe connecté k , selon la définition standard, est connecté ( k - 1 , 0 ) , selon la nouvelle définition. Existe-t-il un algorithme polynomial pour déterminer si G est ( a , b ) connecté? Ici, je considère que l'entrée est G , a et$G$$(a,b)$$a$$b$$G$$k$$(k-1,0)$$G$$(a,b)$$G$$a$ .$b$

Il s'agit d'une version modifiée d'une "réponse" précédente qui a incorrectement revendiqué un algorithme polynomial pour le problème. Ce que j'écris ci-dessous est une connexion à un problème existant qui suggère que le problème est difficile.

Soit deux nœuds dans G et nous voulons vérifier s'ils sont ( a , b ) connectés. Ce enlève tout un des noeuds et des b bords ne doivent pas débrancher s et t . Une autre façon de voir les choses comme suit: quel est le nombre minimum de nœuds que nous devons supprimer pour réduire la connectivité de périphérie entre s et t à $s,t$$G$$(a,b)$$a$$b$$s$$t$$s$$t$$b$? Ces types de problèmes ont été étudiés sous le nom de coupes multi-routes et ce sont des flux doubles à multi-routes. Divers résultats d'approximation ont été montrés bien que de nombreux problèmes de base ne soient pas encore résolus. Un résultat intéressant est le suivant. Supposons que chaque arête ait un coût et nous souhaitons supprimer l'ensemble d'arêtes à coût minimum pour réduire la connectivité des arêtes entre s et t à b ; alors ce problème est NP-Hard lorsque b fait partie de l'entrée. Ce résultat est dans l'article de Barman et Chawla: http://arxiv.org/abs/0908.0350$c(e)$$s$$t$$b$$b$

Deux articles qui paraîtront dans la prochaine SODA 2012 sont sur les coupes multi-routes qui ont d'autres résultats sur le sujet. Celui de Chuzhoy etal a des résultats de dureté pour certaines variantes.