このグラフの問題の複雑さは何ですか?

単純な無向グラフ$ G $が与えられたとき、頂点の部分集合$ A neq emptyset $を見つけます。

  1. A $の任意の頂点$ x について$ x $の隣人の少なくとも半分も$ A $にあり、

  2. $ A $のサイズは最小です。

つまり、すべての内部頂点の少なくとも半分が内部にとどまっているクラスターを探しています。頂点集合$
V(G)$は常にプロパティ1を持つため、このようなクラスタの単なる存在は明らかです。
しかし、最小の(空でない)クラスタを見つけることはどれくらい難しいですか?

この問題の標準名はありますか?その複雑さについては何が分かっていますか?

ベストアンサー

これはクリークからあなたの問題への軽減です。

グラフ$ G $と整数$ k $を$ V = {v_1、v_2、…、v_n }
$とすると、Cliqueのインスタンスから始めます。

Clique remains NPC even under the constraint that $max(deg(v_i))
leq 2(k-1)$ (proof sketch: if $max(deg(v_i) > 2(k-1)$ then add
a $K_t$ where $t = 2(k-1) – max(deg(v_i))$ and connect it to all
nodes of $G$ and ask for a clique of size $k’ = k + t$ in the new
graph).

So we assume that in $G$, $max(deg(v_i)) leq 2(k-1)$. For each
node $v_i$ for which $deg(v_i) < 2(k-1)$ we create an “external”
clique $C_i$ of size $2(k+1)+1$ (every node of $C_i$ clique has at
least $2(k+1)$ neighbours).

$ deg(v_i)$が$ v_i $の次数なら、$ v_i $を$ C_i $の$ 2(k-1) –
deg(v_i)$ノードに接続します。

得られた$ G ‘$において、各$ v_i $は次数$ 2(k-1)$を有する。だから$ | A | geq k
$を指定する必要があります。

It is clear that if one of the vertex of $C_i$ is included in
$A$ then at least $2(k+1)/2 = k+1$ nodes must also be inserted in
it. Note that if an original node has $deg(v_i) < k-1$ then at
least one node of the linked $C_i$ must be included, leading to
$|A| > k$.

最小サイズ$ Aの集合$ A $を構築することができます。 = k $ $ G $に大きさ$ k
$のクリークが含まれている場合に限る。

黄色のノードと太い辺で表されるグラフ$ G $にサイズ$ k = 3
$(三角形)のクリークが含まれているかどうかを調べる還元の例。

satisfactory problem variant 30CC0991E0BCCCD16E41CBD9CD3EEECC

The blue nodes (grouped for better readability) are $K_9$, the
red edges are the links between nodes of $G$ with $deg(v_i) <
2(k-1)$ .

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です