论文标题
完美的外观和斯坦纳循环包装
Perfect Out-forests and Steiner Cycle Packing in Digraphs
论文作者
论文摘要
在本文中，我们研究了两种类型的Digraph包装问题的复杂性：完美的外观问题和Steiner循环包装问题。 对于一个完美的森林问题，我们证明，决定给定的强大挖掘物是否包含1完美的孔洞是NP-HARD。但是，当仅限于半完整的Digraph $ d $时，确定$ d $是否包含$ i $ - 完美的外部forest的问题将成为多项式时间的可求解，其中$ i \ in \ in \ {0,1 \} $。我们还证明，在连接的无环挖掘物中找到最大尺寸的0完美砍伐是NP-HARD，并且在连接的挖掘图中找到最大尺寸的1-完美的最大尺寸的1-完美的孔洞是NP-HARD。 对于Steiner周期包装问题，当两个$ k \ geq 2，\ ell \ geq 1 $都是固定的整数时，我们表明，确定是否至少存在$ \ ell $内部脱节的$ s $ s $ s $ steiner cycles cycles in Eulerian digraph $ d $ d $ d $ d $ d $ d $ np-complete是$ s $ s \ seacseq $ $ s $ s $ s $ k $ k $ s $ s $ s $ s $ s |但是，当我们考虑对称挖掘的类别时，问题就会变成多项式时间。我们还表明，确定至少有$ \ ell $ arc-dischoint指示的$ s $ s $ steiner循环在给定的digraph $ d $中是np-complete，其中$ s \ subseteq v（d）$和$ | s | = k $。
In this paper, we study the complexity of two types of digraph packing problems: perfect out-forests problem and Steiner cycle packing problem. For the perfect out-forest problem, we prove that it is NP-hard to decide whether a given strong digraph contains a 1-perfect out-forest. However, when restricted to a semicomplete digraph $D$, the problem of deciding whether $D$ contains an $i$-perfect out-forest becomes polynomial-time solvable, where $i\in \{0,1\}$. We also prove that it is NP-hard to find a 0-perfect out-forest of maximum size in a connected acyclic digraph, and it is NP-hard to find a 1-perfect out-forest of maximum size in a connected digraph. For the Steiner cycle packing problem, when both $k\geq 2, \ell\geq 1$ are fixed integers, we show that the problem of deciding whether there are at least $\ell$ internally disjoint directed $S$-Steiner cycles in an Eulerian digraph $D$ is NP-complete, where $S\subseteq V(D)$ and $|S|=k$. However, when we consider the class of symmetric digraphs, the problem becomes polynomial-time solvable. We also show that the problem of deciding whether there are at least $\ell$ arc-disjoint directed $S$-Steiner cycles in a given digraph $D$ is NP-complete, where $S\subseteq V(D)$ and $|S|=k$.
