Minimum leaf out-branching and related problems
Minimum leaf out-branching and related problems
复制标题
DOI：
10.1016/j.tcs.2009.03.036
复制
发表时间：
2008-01
期刊：
影响因子：
--
通讯作者：
G. Gutin;Igor Razgon;Eun Jung Kim
中科院分区：
文献类型：
--
作者：
G. Gutin;Igor Razgon;Eun Jung Kim
给定一个有向图D，最小叶子分支问题（MinLOB）是在D中找到一个具有最小可能叶子数量的分支的问题，即，出度为0的顶点。证明了MinLOB对于无圈有向图是多项式时间可解的。在一般情况下，MinLOB是NP-难的，我们认为三个参数化的MinLOB。我们证明了其中两个是NP-完全的每一个值的参数，但第三个是固定参数易处理（FPT）。FPT参数化如下：给定一个n阶有向图D和一个正整数参数k，检查D是否包含一个最多有n-k个叶子的出分支（如果存在，则找到这样的出分支）。我们找到了一个O（k2）阶的问题核，构造了一个O（2 O（klogk）+n6）的算法，它是一个“可加”的FPT算法.我们还考虑了从两个相关的问题，最小路径覆盖和最大内部出树问题到MinLOB的转换，这意味着这两个问题的一些参数化也是FPT的。
Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We prove that MinLOB is polynomial-time solvable for acyclic digraphs. In general, MinLOB is NP-hard and we consider three parameterizations of MinLOB. We prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parameterization is as follows: given a digraph D of order n and a positive integral parameter k, check whether D contains an out-branching with at most n−k leaves (and find such an out-branching if it exists). We find a problem kernel of order O(k2) and construct an algorithm of running time O(2O(klogk)+n6), which is an ‘additive’ FPT algorithm. We also consider transformations from two related problems, the minimum path covering and the maximum internal out-tree problems into MinLOB, which imply that some parameterizations of the two problems are FPT as well.