The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110: 47-66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate t...
详细信息
ISBN:
(纸本)9783319286846;9783319286839
The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110: 47-66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width;for an input n-vertex graph G and an integer w, our algorithm either confirms that the tree-cut width of G is more than w or returns a tree-cut decomposition of G certifying that its tree-cut width is at most 2w, in time 2(O(w2 log w)) . n(2). Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known.
In this paper, we introduce a problem called MINIMUM SUBTREE PROBLEM WITH DEGREE WEIGHTS, or MTDW. This problem generalized covering tree problems like SPANNING TREE, STEINER TREE, MINIMUM BRANCH VERTICES, MINIMUM LEA...
详细信息
In this paper, we introduce a problem called MINIMUM SUBTREE PROBLEM WITH DEGREE WEIGHTS, or MTDW. This problem generalized covering tree problems like SPANNING TREE, STEINER TREE, MINIMUM BRANCH VERTICES, MINIMUM LEAF SPANNING TREE, or PRIZE COLLECTING STEINER TREE. It consists, given an undirected graph G = (V, E), a set of m + 1 mappings C-1, C-2,...,C-m, D : V x N -> Z, a set of m integers K-1, K-2,...,K-m is an element of Z and a positive integer l, in the search of a forest (T-1,T-2,...,T-l) containing l node-disjoint trees of G. Along with K-l, the mapping C-l defines a constraint that should be satisfied by the trees of the forest. For each tree T-l, it associates each node n of V to the score C-l (upsilon,dT(l)(upsilon)) where d(Tl) (upsilon) is the degree of upsilon in T-l (possibly 0 if the node is not in T-l). The sum Sigma(upsilon is an element of V) C-j(upsilon, d(Tt)(upsilon)) should not exceed K-j. In addition, the forest should minimize Sigma(l)(t=1) Sigma(upsilon is an element of V) D(upsilon,dT(l) (upsilon)). We proceed to a parameterized analysis of the MTDW problem with regard to four parameters that are the number of constraints m, the value l, the treewidth of the input graph G and Delta, the minimum degree above which all the constraints and D are constant (for every j is an element of[1,m], upsilon is an element of V and d >= Delta, C-j(upsilon,d) = C-j(upsilon,Delta), and D(upsilon,d) = D(upsilon,Delta)). For this problem, we provide a first dichotomy P versus NP-hard depending whether the previous parameters are fixed to be constant or not and a second dichotomy FPT versus W[1]-hard depending whether each of these parameters is constant, considered as a parameter, or disregard. As a side effect, we obtained parameterized algorithms, previously undescribed, for problems such that BUDGET STEINER TREE PROBLEM WITH PROFITS, MINIMUM BRANCH VERTICES, GENERALIZED BRANCH VERTICES, or k-BOTTLENECK STEINER TREE.
暂无评论