论文标题
超图中的Steiner连接问题
Steiner connectivity problems in hypergraphs
论文作者
论文摘要
我们说，如果$ s \ subseteq v（t）$，树$ t $是$ s $ steiner树，如果可以将$ s $ s $ steiner Hyperree缩小到$ s $ s $ steiner树，则HyperGraph为$ S $ STEINER HYPERTREE。我们证明，确定一个NP份额，给定一个HyperGraph $ \ MATHCAL {H} $和一些$ S \ subseteq V（\ Mathcal {H}）$，是否有$ \ Mathcal {H} $的subhypergraph，这是$ s $ s $ s $ s $ s $ steiner hypretree。作为推论，我们为超图中的两个施泰纳方向问题给出了两个负面结果。首先，我们证明，确定np $ \ Mathcal {h} $，v（\ Mathcal {h}）$和一些$ s \ subseteq v（\ Mathcal {h}）$是$ r \ in np-Complete。其次，我们证明，鉴于HyperGraph $ \ Mathcal {H} $和一些$ S \ subseteq V（\ Mathcal {h}）$，确定是NP的完整，该超透明率是否具有方向，在$ S $中的任何两个角度是否可以相互互动。这回答了Egerváry研究小组的长期开放问题。我们进一步表明，确定给定的超图是否具有均衡的方向是NP的完整。从积极的一面来看，我们表明，如果终端数量$ | s | $固定，则可以在多项式时间内解决施泰纳乳房和第一个方向问题的问题。
We say that a tree $T$ is an $S$-Steiner tree if $S \subseteq V(T)$ and a hypergraph is an $S$-Steiner hypertree if it can be trimmed to an $S$-Steiner tree. We prove that it is NP-complete to decide, given a hypergraph $\mathcal{H}$ and some $S \subseteq V(\mathcal{H})$, whether there is a subhypergraph of $\mathcal{H}$ which is an $S$-Steiner hypertree. As corollaries, we give two negative results for two Steiner orientation problems in hypergraphs. Firstly, we show that it is NP-complete to decide, given a hypergraph $\mathcal{H}$, some $r \in V(\mathcal{H})$ and some $S \subseteq V(\mathcal{H})$, whether this hypergraph has an orientation in which every vertex of $S$ is reachable from $r$. Secondly, we show that it is NP-complete to decide, given a hypergraph $\mathcal{H}$ and some $S \subseteq V(\mathcal{H})$, whether this hypergraph has an orientation in which any two vertices in $S$ are mutually reachable from each other. This answers a longstanding open question of the Egerváry Research group. We further show that it is NP-complete to decide if a given hypergraph has a well-balanced orientation. On the positive side, we show that the problem of finding a Steiner hypertree and the first orientation problem can be solved in polynomial time if the number of terminals $|S|$ is fixed.
