A knot $K$ in a directed graph $D$ is a strongly connected component of size at least two such that there is no arc $(u,v)$ with $u \in V(K)$ and $v\notin V(K)$. Given a directed graph $D=(V,E)$, we study Knot-Free Vertex Deletion (KFVD), where the goal is to remove the minimum number of vertices such that the resulting graph contains no knots. This problem naturally emerges from its application in deadlock resolution since knots are deadlocks in the OR-model of distributed computation. The fastest known exact algorithm in literature for KFVD runs in time $\mathcal{O}^\star(1.576^n)$. In this paper, we present an improved exact algorithm running in time $\mathcal{O}^\star(1.4549^n)$, where $n$ is the number of vertices in $D$. We also prove that the number of inclusion wise minimal knot-free vertex deletion sets is $\mathcal{O}^\star(1.4549^n)$ and construct a family of graphs with $\Omega(1.4422^n)$ minimal knot-free vertex deletion sets
翻译：在有向图 $D=(V,E)$ 中，一个$K$结是指一个强连通分量，其大小至少为两个点，且没有一条有向边 $(u,v)$，其中 $u \in V(K)$ 且 $v\notin V(K)$。给定有向图 $D$，我们研究了无结点顶点删除（KFVD）问题，即删除最小数量的顶点，使结果图不包含结点。该问题自然地衍生自其在死锁解决中的应用，因为结点是分布式计算中的死锁。文献中已知的 KFVD 最快的精确算法运行时间为 $\mathcal{O}^\star(1.576^n)$。在本文中，我们提出了一种改进的精确算法，它的运行时间为 $\mathcal{O}^\star(1.4549^n)$，其中 $n$ 是 $D$ 中的顶点数。我们还证明了包含至少的最小无结点顶点删除集数量为 $\mathcal{O}^\star(1.4549^n)$，并构造了一个具有 $\Omega(1.4422^n)$ 个最小无结点顶点删除集的图族。
相关内容
微信扫码咨询专知VIP会员