Every connected graph on n vertices has a cut of size at least n - 1. We call this bound the spanning tree bound. In the MAX-CUT ABOVE SPANNING TREE (MAXCUT-AST) problem, we are given a connected n-vertex graph G and ...
详细信息
Every connected graph on n vertices has a cut of size at least n - 1. We call this bound the spanning tree bound. In the MAX-CUT ABOVE SPANNING TREE (MAXCUT-AST) problem, we are given a connected n-vertex graph G and a non-negative integer k, and the task is to decide whether G has a cut of size at least n - 1 + k. We show that MAX-CUT-AST admits an algorithm that runs in time O(8kn O(1)), and hence it is fixedparametertractable with respect to k. Furthermore, we show that MAX-CUT-AST has a polynomial kernel of size O(k5).
Scheduling problems involving a set of dependent tasks with release dates and deadlines on a limited number of resources have been intensively studied. However, few parameterized complexity results exist for these pro...
详细信息
Scheduling problems involving a set of dependent tasks with release dates and deadlines on a limited number of resources have been intensively studied. However, few parameterized complexity results exist for these problems. This paper studies the existence of a feasible schedule for a typed task system with precedence constraints and time intervals (r(i), d(i)) for each job i. The problem is denoted by P|M-j (type), prec, r(i), d(i)|*. Several parameters are considered: the pathwidth pw(I) of the interval graph I associated with the time intervals (r(i), d(i)), the maximum processing time of a task p(max) and the maximum slack of a task sl(max). This paper establishes that the problem is para-NP-complete with respect to any of these parameters. It then provides a fixed-parameteralgorithm for the problem parameterized by both parameters pw(I) and min(p(max), sl(max)). It is based on a dynamic programming approach that builds a levelled graph which longest paths represent all the feasible solutions. fixed-parameteralgorithms for the problems P|M-j (type), prec, r(i), d(i) |Cmax and P|M-j (type), prec, r(i) |L-max are then derived using a binary search.
We study single-item discrete multi-module capacitated lot-sizing problems without and with backlogging where the amount produced in each time period is equal to the summation of binary multiples of the capacities of ...
详细信息
We study single-item discrete multi-module capacitated lot-sizing problems without and with backlogging where the amount produced in each time period is equal to the summation of binary multiples of the capacities of n available different modules (or machines). For fixed n >= 2, we develop fixed-parametertractable (polynomial) exact algorithms that generalize the algorithms of van Vyve (2007) for n = 1. We utilize these algorithms within a Lagrangian decomposition framework to solve their multi-item versions. Our algorithms are computationally efficient and stable, in comparison to Gurobi 9.0. (C) 2022 Elsevier B.V. All rights reserved.
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.
We consider the following natural "above-guarantee"" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G and integer k, the Longest Detour problem asks for an...
详细信息
We consider the following natural "above-guarantee"" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G and integer k, the Longest Detour problem asks for an (s, t)-path in G that is at least k longer than a shortest (s, t)-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parametertractable on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time 2(O(k))center dot n(O(1)). Up to the base of the exponential, this running time matches the best algorithms for finding a path of length at least k. Furthermore, we study the related EXACT DETOUR problem, which asks whether a graph G contains an (s, t)-path that is exactly k longer than a shortest (s, t)-path. For this problem, we obtain randomized algorithms with running times 2.746(k) center dot n(O(1)) (for undirected graphs) and 4(k) center dot n(O(1)) (for directed graphs) and a deterministic algorithm with running time 6.745(k) center dot n(O(1)), showing that this problem is fixed-parametertractable as well.
The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin 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 tha...
详细信息
The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin 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 . 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.
Tree-width and clique-width are two important graph complexity measures that serve as parameters in many fixed-parameter tractable algorithms. We give two algorithms that transform tree-decompositions represented by n...
详细信息
Tree-width and clique-width are two important graph complexity measures that serve as parameters in many fixed-parameter tractable algorithms. We give two algorithms that transform tree-decompositions represented by normal trees into clique-width terms (a rooted tree is normal for a graph if its nodes are the vertices of the graph and every two adjacent vertices are on a path of the tree starting at the root). As a consequence, we obtain that, for certain classes of sparse graphs, clique-width is polynomially bounded in terms of tree-width. It is even linearly bounded for planar graphs and incidence graphs. These results are useful in the construction of model-checking algorithms for problems described by monadic second-order formulae, including those allowing edge set quantifications. (C) 2017 Elsevier B.V. All rights reserved.
We design FPT-algorithms for the following problems. The first is LIST DIGRAPH HOMOMORPmsm: given two digraphs G and H, with order n and h, respectively, and a list of allowed vertices of H for every vertex of G, does...
详细信息
We design FPT-algorithms for the following problems. The first is LIST DIGRAPH HOMOMORPmsm: given two digraphs G and H, with order n and h, respectively, and a list of allowed vertices of H for every vertex of G, does there exist a homomorphism from G to H respecting the list constraints? Let be the number of edges of G mapped to non-loop edges of H. The second problem is MIN-MAx MumwAY CUT: given a graph G, an integer l >= 0, and a set T of r terminals, can we partition V (G) into r parts such that each part contains one terminal and there are at most t edges with only one endpoint in this part? We solve both problems in time 2O(*** h+l(2).log l) . n(4) . log n and 2O((lr)(2) log lr) . n(4) . log n, respectively, via a reduction to a new problem called LIST ALLOCATION, which we solve adapting the randomized contractions technique of Chitnis et al. (2012) [4]. (C) 2017 Elsevier Inc. All rights reserved.
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 the IMBALANCE MINIMIZATION problem we are given a graph G = (V, E) and an integer b and asked whether there is an ordering v(1) ... v(n) of V such that the sum of the imbalance of all the vertices is at most b. The...
详细信息
In the IMBALANCE MINIMIZATION problem we are given a graph G = (V, E) and an integer b and asked whether there is an ordering v(1) ... v(n) of V such that the sum of the imbalance of all the vertices is at most b. The imbalance of a vertex v(i) is the absolute value of the difference between the number of neighbors to the left and right of v(i). The problem is also known as the BALANCED VERTEX ORDERING problem and it finds many applications in graph drawing. We show that this problem is fixedparametertractable and provide an algorithm that runs in time 2(O (b log b)) . n(O (1)). This resolves an open problem of Kara et al. [On the complexity of the balanced vertex ordering problem, in: COCOON, in: Lecture Notes in Comput. Sci., vol. 3595, 2005, pp. 849-858]. (C) 2013 Elsevier B.V. All rights reserved.
暂无评论