Какова сложность этой проблемы графа?

Для простого неориентированного графа $G$ найдите подмножество $A\neq \emptyset$ вершин, такое что

для любой вершины хотя бы половина соседей также находится в , и $x\in A$ $x$ $A$
размер $A$ минимален.

То есть мы ищем кластер, в котором по крайней мере половина окрестности каждой внутренней вершины остается внутренней. Само существование такого кластера очевидно, поскольку все множество вершин $V(G)$ всегда обладает свойством 1. Но насколько сложно найти самый маленький (непустой) такой кластер?

Есть ли стандартное название для этой проблемы? Что известно о его сложности?

graph-theory graph-algorithms np-hardness Андрас Фараго
источник

Кажется, вариант Удовлетворительной проблемы с разделами . Я не знаю, известен ли ваш вариант и был ли он NPC; но, вероятно, сработает сокращение от k-клики: свяжите каждый узел

исходного графа с

узлами

«внешней клики» размера

(каждый узел имеет свою внешнюю клику). Тогда вы можете найти нетривиальное множество

размера

тогда и только тогда, когда a

v_{i}

$v_i$

k + 1

$k+1$

C_{i}

$C_i$

2 (k + 1)

$2(k+1)$

A

$A$

k

$k$

k

$k$ -clique существует в исходном графе (вы должны выбрать хотя бы узел, но вы должны избегать любой внешней клики). Но это всего лишь идея; если у меня будет достаточно времени, я постараюсь проверить правильность сокращения.

Марцио Де Биаси

@MarzioDeBiasi Спасибо, после некоторого поиска я обнаружил, что проблема удовлетворительного разбиения действительно связана. Однако в каждом варианте, который я мог найти, они ищут раздел, а не отдельный набор. Непонятно, как они связаны. В вашем сокращении, если я что-то не понял,

клик исходного графа не удовлетворяет определению, так как каждый узел в нем будет иметь

внутренних соседей, но по крайней мере

внешних соседей из-за добавленного внешнего клики.

k

$k$

k - 1

$k-1$

k + 1

$k+1$

Андрас Фараго

Я думаю, что эта проблема известна как «оборонительный альянс»

Даниелло

@daniello: отлично, я искал в опросе IG Yero, JA Rodriguez-Velazquez, «Оборонительные альянсы на графиках: опрос», 2013, но не нашел слова «половина»; когда у меня будет достаточно времени, я внимательно прочитаю; вполне вероятно, что проблема ОП уже известна!

Марцио Де Биаси

Кажется, это сформулировано как «каждая вершина имеет как минимум столько же соседей внутри, сколько снаружи», что совпадает с вопросом до округления, и, возможно, включает / не включает в себя саму вершину в подсчете

Даниелло

Ответы:

Это сокращение от клики к вашей проблеме.

Начнем с экземпляром Clique: граф и целое число , пусть . $G$ $k$ $V = \{ v_1, v_2,...,v_n\}$

Клика остается NPC даже при условии, что (контрольный эскиз: если затем добавьте где $max(deg(v_i)) \leq 2(k-1)$ $max(deg(v_i) > 2(k-1)$ $K_t$ и соедините его со всеми узлами и попросите клику размером в новом графе). $t = 2(k-1) - max(deg(v_i))$ $G$ $k' = k + t$

Таким образом , мы предполагаем , что в , . Для каждого узла для которого мы создаем «внешнюю» клику размера (каждый узел $G$ $max(deg(v_i)) \leq 2(k-1)$ $v_i$ $deg(v_i) < 2(k-1)$ $C_i$ $2(k+1)+1$ $C_i$ clique has at least $2(k+1)$ neighbours).

If $deg(v_i)$ is the degree of $v_i$ , we connect $v_i$ to $2(k-1) - deg(v_i)$ nodes of $C_i$ .

В полученном каждый имеет степень ; так потому что должна быть выбрана хотя бы одна вершина. $G'$ $v_i$ $2(k-1)$ $|A| \geq k$

Ясно, что если одна из вершин включена в то в нее также должны быть вставлены не менее узлов. Обратите внимание, что если исходный узел имеет то должен быть включен по крайней мере один узел связанного , что приводит к . $C_i$ $A$ $2(k+1)/2 = k+1$ $deg(v_i) < k-1$ $C_i$ $|A| > k$

Таким образом, мы можем построить набор минимального размера тогда и только тогда, когда содержит клику размера . $A$ $|A| = k$ $G$ $k$

Пример сокращения, в котором мы спрашиваем, содержит ли граф представленный желтыми узлами и полужирными ребрами, клику размером (треугольник). $G$ $k = 3$

Синие узлы (сгруппированные для лучшей читаемости) - это , красные края - это связи между узлами с . $K_9$ $G$ $deg(v_i) < 2(k-1)$

Marzio De Biasi
источник

G^{'}

$G'$

\geq 2 (k - 1)

$\geq 2(k-1)$ by construction, so if

A

$A$ contain one vertex, it must contain at least

2 (k - 1) / 2 = k - 1

$2(k-1)/2 = k-1$ neighbours (and the same applies to all vertices of

A

$A$ ), so

| A | \geq k

$|A| \geq k$ . The "minimum size"

k

$k$ can be achieved only if

A

$A$ is a clique of size

k

$k$ .

Marzio De Biasi

@WillardZhan: I added another condition to the starting clique problem (but it should remains NPC) ... I'm still checking it (not entirerly convinced its correct).

Marzio De Biasi

Yes, now it works perfectly (though it should be

k^{'}

$k'$ in the expression of

t

$t$ ). Maybe I shall delete my comments?

Willard Zhan

@WillardZhan: I think it's correct, because in that paragraph I'm referring to the reduction from Clique [instance

(G, k)

$(G,k)$ ] to Clique+constraint

m a x (d e g (v_{i})) \leq 2 (k - 1)

$max(deg(v_i)) \leq 2(k-1)$ [instance

(G^{'}, k^{'})

$(G',k')$ ].

t

$t$ is the number of the nodes (clique) to add to G to get the new instance of Clique that stastisfies the constraint.

Marzio De Biasi