论文标题
列举连接的主导集
Enumerating Connected Dominating Sets
论文作者
论文摘要
列举所有纳入最小联系的统治集的问题在$ n $的时间表中显着少于$ 2^n $，这是一个开放的问题，在许多地方都被提出。我们通过提供$ \ Mathcal {o}（1.9896^n）$的枚举算法来肯定地回答了这个问题，仅使用多项式空间。此结果的关键是在2级图上考虑了此枚举问题，这在时间上被证明是可能的$ \ Mathcal {O}（1.9767^n）$。我们还通过构建$ω（1.4890^n）$ n $的订单$ n $的图表来显示新的下限结果，而最小连接的主导集，而先前的示例获得了$ω（1.4422^n）$。我们的施工导致一些特殊的图形类别的下限。 我们还解决了有关输出敏感枚举的基本问题。也就是说，我们给出了为什么无法将我们的算法变成枚举算法的原因，该算法可以保证在没有太多努力的情况下保证多项式延迟。更准确地说，我们证明，如果存在最小的连接$ d $，即使$ u \ subseteq d $，即使$ g $，即使$ g $已知，因此，如果存在最小的连接$ d $，则决定了$ g $和顶点套装$ u $是NP的组件。我们的还原还表明，对于列举最小连接的主导集，即使任何次指数延迟也不容易实现。另一个还原表明，对于这个扩展问题，就最小的连接统治集（由$ | u | $）进行了参数，因此对于此扩展问题，没有预期的fpt-algorithms。 We also relate our enumeration problem to the famous open Hitting Set Transversal problem, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic solution to the Hitting Set Transversal problem.
The question to enumerate all inclusion-minimal connected dominating sets in a graph of order $n$ in time significantly less than $2^n$ is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time $\mathcal{O}(1.9896^n)$, using polynomial space only. The key to this result is the consideration of this enumeration problem on 2-degenerate graphs, which is proven to be possible in time $\mathcal{O}(1.9767^n)$. We also show new lower bound results by constructing a family of graphs of order $n$ with $Ω(1.4890^n)$ minimal connected dominating sets, while previous examples achieved $Ω(1.4422^n)$. Our construction results in lower bounds for a few special graph classes. We also address essential questions concerning output-sensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much efforts. More precisely, we prove that it is NP-complete to decide, given a graph $G$ and a vertex set $U$, if there exists a minimal connected dominating set $D$ with $U\subseteq D$, even if $G$ is known to be 2-degenerate. Our reduction also shows that even any subexponential delay is not easy to achieve for enumerating minimal connected dominating sets. Another reduction shows that no FPT-algorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by $|U|$. We also relate our enumeration problem to the famous open Hitting Set Transversal problem, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic solution to the Hitting Set Transversal problem.
