ハイパーグラフのスパニング・ハイパーフォレストのルートセットを最小化する

私は$ k
$ハイパーグラフのスパニング・ハイパーフォレスト(すべての頂点をカバーするハイパーツリーの集合体)を含む問題の複雑さに興味があります。下のハイパーグラフの関連定義について説明しますが、以下は

指定されたハイパーグラフ$ D $と整数$ k geqslant 1 $に対して、ルートセットがある$ D
$に対するスパニングハイパーフォレストが存在するかどうかを判断します。

HYPERFOREST ROOT SETをスパニングします。サイズは多くとも$ k
$です。

Remarks.

  • It is not difficult to show that
    SPANNING HYPERFOREST ROOT SET is in
    NP: in particular, if a root-set of the suitable
    size is provided, then a spanning hyperforest with that root-set
    can be found in polynomial time.
  • It is also trivial to find a value of $k$ for which $(D,k)$ is
    a YES instance: for instance $k = lvert V(D) rvert$ (in which
    case the empty hypergraph is a spanning hyperforest with root set
    $k$).
  • Considered as an optimisation problem, it is usually easy to
    find values $k < lvert V(D) rvert$ for which $(D,k)$ remain
    YES instances, though it is not clear how easily one can find the
    optimum.

質問。

Is SPANNING HYPERFOREST ROOT SET also
NP-hard? Is this true in the special case where
the input hypergraph is “symmetric”, in the sense that for any edge
$e = (t(e), h(e))$ and for any $v in s(e) := t(e) cup h(e)$,
there is also an edge $e’ = (s(e) {,smallsetminus,} {v},
v)$?


関連定義。

以下では、「ハイパーグラフ上のフローの定義に従っている」[
Cambini、Gallo、Scutellàのhref =
“https://pdfs.semanticscholar.org/13cf/dff5b9389d3ca511caf9358fd2b3f13c0c11.pdf”
rel = “nofollow noreferrer”>無料PDFリンクをご覧ください。

  • A hypergraph is a pair $G = (V,E)$, where $E subseteq mathcal
    P(V)$. If each $ein E$ has the same cardinality $k$, we call $G$ a
    $k$-uniform hypergraph (or $k$-hypergraph).
  • A directed hypergraph is a pair $D = (V,E)$, where in our
    setting we let $E subseteq mathcal P(V) times V$ be the set of
    hyper-edges. For each edge $e in E$, we let $t(e) = pi_1(e)
    subseteq V$ be the “tail” of the edge, and $h(e) = pi_2(e) in V
    smallsetminus t(e)$ be the “head” of the edge. Thus we consider
    hypergraphs where each edge has exactly one head (more general
    definitions are common).
  • We may associate a “symmetric” directed hypergraph $D_G =
    (V,E’)$ of this sort to any hypergraph $G = (V,E)$, by replacing
    each undirected edge $e in E$ with a collection of directed
    variants $E’_e = { (e{,smallsetminus,} v, v) ,vert, v in e
    }$ and letting $E’ = bigcup_{e in E} E’_e$.
  • A directed cycle in a directed hypergraph $D = (V,E)$ is just a
    vertex sequence $(v_0,v_1,ldots,v_ell)$ for which $v_{i+1} ne
    v_i$ for $0 leqslant i < ell$, $v_0 = v_ell$, and for which
    for each $0 leqslant i < ell$ there is an edge $e_ell$ for
    which $v_i in t(e_i)$ and $v_{i+1} = h(e_i)$.

  • A hyperforest is a directed hypergraph in which all vertices
    have in-degree either zero or one, and which has no cycles in the
    above sense. (N.B. I am diverging here from the
    terminology in my reference above, which does not explicitly
    consider whether the hypergraph is connected; but this cannot be
    taken for granted in my setting.) The set of nodes of in-degree
    zero we call the “root set” of the hyperforest.

  • A spanning hyperforest $T$ for a directed hypergraph $D =
    (V,E)$, is simply a subgraph $T subseteq D$ of the hypergraph
    which contains all of the vertices $V$ and which is a
    hyperfohrest.

ベストアンサー

この答えは、SPANNING SYMMETRIC HYPERFOREST ROOT
SET(SSHRS)問題のNP硬度を扱っています(無向ハイパーグラフ$ G $と数値$ k
$を仮定しています)。対称指示ハイパーグラフ$ D_G $)。

我々は、この問題は、唯一の最大限の双対マッチング(MURBM)の問題(硬度についてはhttps://link.springer.com/article/10.1007/s00453-001-0004-z
を参照してください)。グラフ$ B $内の一意に制限されたマッチングは、$ M $の頂点に対する$ B
$の誘導部分グラフが完全に1つの完全一致($ M $自体)を持つように一致する$ M $です。
MURBM問題は、与えられた2部グラフ$ B $と与えられた数$ n $に対して少なくとも$ n
$辺を持つグラフに一意に制限された一致が存在するかどうかを尋ねる。

マッチングは、グラフ内に、マッチング中とマッチング中とで交互に繰り返されるサイクルが存在しない場合に限り、一意に制限されることに注意してください。
(これは簡単に表示されるので、ここでは証明は含まれません)。

MURBMからSSHRSへの削減は簡単です。バイパートグラフ$ B $と番号$ n
$からなるMURBMインスタンスが与えられます。 $ B $に頂点部分$ V_1 $と$ V_2 $があるとします。 $
N(v)$を$ B $の$ v $の近傍の集合と定義する。次に、頂点$ V = V_1 $とエッジ$ E = {N(v)〜|〜v
をV_2 } $でハイパーグラフ$ G =(V、E)$を定義します。次に、$ k = | V_1 | – n
$。言い換えれば、二分グラフモデルが$ B $であるハイパーグラフ$ G $を構築する。縮小のSSHRSインスタンス出力として$ G
$と$ k $を出力します。

削減の背景にあるロジックは次のとおりです。

$ D_G $でスパニング・ハイパーフォレストを選択することは、特定の制約のもとで$ D_G
$のエッジの集合を選択することと同じです。しかし、$ D_G $の辺の集合を選択することは、$ G
$の辺の集合を選択し、頂点を頂点とすることと等価です。ハイパーフォレストはサイクルを許さないので、$ G
$の異なるエッジで同じエッジを使うことはできません(そのような2つの
“重複”エッジがサイクルを形成するため)。ハイパーフォレストでは、頂点は最大次数1を持つので、同じ頂点を複数の異なるエッジの頭として選択することはできません。言い換えれば、スパンニング・ハイパーフォレストの選択を構成する$
G $のエッジの選択とエッジの選択は、$ G
$の二部グラフ・モデルのマッチングの選択と同じです(特定の制約の影響を受けます)。しかし、建設によって、$ G
$の二部グラフモデルはまさに二部グラフ$ B $なので、$ D_G $でスパニング森林を選択することは、特定の制約のもとで$ B
$でのマッチングを選択することと同じです。

これらの制約は何ですか?まあ、ハイパーフォレストはサイクルを持つことはできませんし、頂点の度数を1以下にする必要があります。頂点のin-degree制約は既にどのマッチングでも満たされているため、サイクルを持たないという唯一の制約があります。しかし、ハイパーフォレストのサイクルは、$
G
$の2部グラフモデルの1サイクルに対応し、すべての第2エッジが対応する「マッチング」にある。このように、ハイフォレストのサイクルフリー条件は、マッチングにあるか否かのエッジの交互するグラフにサイクルが存在しないという条件と等価である。

したがって、$ G $の超森林は、$ B
$の一意に制限されたマッチングに対応します。残っているのは、パラメータが一致していることを示すことです。ルートセットサイズが少なくとも$
k $の超森林を持つことは、少なくとも$ n
$以上のサイズのマッチングに相当します。スパニング・ハイパーフォレストの各頂点は0度または1度のいずれかの度合いを持つので、度数1の頂点の数はスパニング・ハイパーフォレストのイン・ディグの合計に等しくなります。しかし、インジケータの総数は、各エッジが正確に1つのヘッドを有するので、エッジの数にも等しい。したがって、スパニング・ハイパーフォレストにおけるイン・ディグリー-1頂点の数は、エッジの数に等しい。マッチングのサイズは、超森林内のエッジの数に等しいこともわかります。従って、マッチングのサイズは、超森林内の度数1の頂点の数に等しい。さらに、根の数は、定義によれば、0度の頂点の数である。したがって、ルートセットのサイズにマッチングのサイズを加えたものは、頂点の数$
| V |に等しい。 = | V_1 | $。したがって、ハイパーフォレストのルートセットサイズは、最大$ k = | V_1 | –
一致が少なくとも$ n $以上のサイズの場合に限り、n $。

返信を残す

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