Связность графов удалением ребер и вершин

Будем говорить , что граф является ( , б ) связным , если удаление любых через вершины и любые б ребер из G листьев всегда связного графа. Например, k- связный граф, согласно стандартному определению, ( k - 1 , 0 ) -связный, согласно новому определению. Существует ли алгоритм полиномиальное время , чтобы решить , если G является ( , б ) связным? Здесь я считаю, что вход G , а и$G$$(a,b)$$a$$b$$G$$k$$(k-1,0)$$G$$(a,b)$$G$$a$ .$b$

Это отредактированная версия предыдущего «ответа», в котором неправильно задан алгоритм задачи за полиномиальное время. То, что я пишу ниже, является связью с существующей проблемой, которая предполагает, что проблема трудна.

Позволять два узла в G, и мы хотим проверить, связаны ли они ( a , b ) . То есть удаление любыхузлов a и любыхребер b не должно разъединять s и t . Другой способ взглянуть на это следующим образом: какое минимальное количество узлов нам нужно удалить, чтобы уменьшить граничную связность между s и t до$s,t$$G$$(a,b)$$a$$b$$s$$t$$s$$t$$b$? Проблемы такого типа были изучены под названием «многоуровневые разрезы», и они двойственны многопутевым потокам. Были показаны различные результаты аппроксимации, хотя многие основные проблемы еще не решены. Интересным результатом является следующее. Предположим, что каждое ребро имеет стоимость и мы хотим удалить набор ребер с минимальной стоимостью, чтобы уменьшить связность ребер между s и t до b ; тогда эта проблема NP-Hard, когда b является частью ввода. Этот результат содержится в статье Бармена и Чавлы: http://arxiv.org/abs/0908.0350$c(e)$$s$$t$$b$$b$

Две статьи, которые появятся в предстоящем SODA 2012, посвящены многопрофильным сокращениям, которые дают дальнейшие результаты по этой теме. У Чужого этала результаты твердости для некоторых вариантов.