检索结果-内蒙古大学图书馆

fixed-parameter tractable algorithm and Polynomial Kernel for Max-Cut Above Spanning Tree

THEORY OF COMPUTING SYSTEMS 2020年第1期64卷 62-100页

作者： Madathil, Jayakrishnan Saurabh, Saket Zehavi, Meirav Homi Bhabha Natl Inst Inst Math Sci Chennai Tamil Nadu India Univ Bergen Dept Informat Bergen Norway Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

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 fixed parameter tractable with respect to k. Furthermore, we show that MAX-CUT-AST has a polynomial kernel of size O(k5).

关键词： Max-Cut Above guarantee parameterization fixed-parameter tractable algorithm Polynomial kernel

来源：评论

学校读者我要写书评

暂无评论

fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines

引用

JOURNAL OF SCHEDULING 2024年第2期27卷 119-133页

作者： Hanen, Claire Kordon, Alix Munier Sorbonne Univ CNRS LIP6 F-75005 Paris France Univ Paris Nanterre UPL F-92000 Nanterre France

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-parameter algorithm 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-parameter algorithms 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.

关键词： fixed-parameter tractable algorithm Precedence constraints Typed task system

来源：评论

学校读者我要写书评

暂无评论

Discrete multi-module capacitated lot-sizing problems with multiple items

引用

OPERATIONS RESEARCH LETTERS 2022年第2期50卷 168-175页

作者： Kulkarni, Kartik Bansal, Manish Virginia Tech Dept Ind & Syst Engn 250 Durham Hall1145 Perry St Blacksburg VA 24060 USA

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-parameter tractable (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.

关键词： Multi-module capacitated lot-sizing with backlogging Multi-item discrete lot-sizing problem fixed-parameter tractable algorithm Concave production and holding costs Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth

引用

THEORETICAL COMPUTER SCIENCE 2024年 990卷

作者： Baste, Julien Watel, Dimitri Univ Lille CNRS Cent Lille UMR 9189CRIStAL F-59000 Lille France ENSIIE 1 Sq Resistance F-91000 Evry France Telecom SudParis SAMOVAR 9 Rue Charles Fourier F-91000 Evry France

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.

关键词： fixed-parameter tractable algorithm Graph algorithm Spanning tree problems Treewidth

来源：评论

学校读者我要写书评

暂无评论

FINDING DETOURS IS fixed-parameter tractable

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第4期33卷 2326-2345页

作者： Bezakova, Ivona Curticapean, Radu Dell, Holger Fomin, Fedor, V Rochester Inst Technol Dept Comp Sci Rochester NY 14623 USA Basic Algorithms Res Copenhagen Copenhagen Denmark IT Univ Copenhagen Copenhagen Denmark Univ Bergen Dept Informat N-5020 Bergen Norway

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-parameter tractable 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-parameter tractable as well.

关键词： longest path fixed-parameter tractable algorithm above-guarantee parameterization graph minors

来源：评论

学校读者我要写书评

暂无评论

An FPT 2-Approximation for Tree-Cut Decomposition

引用

algorithmICA 2018年第1期80卷 116-135页

作者： Kim, Eun Jung Oum, Sang-il Paul, Christophe Sau, Ignasi Thilikos, Dimitrios M. CNRS LAMSADE Paris France Korea Adv Inst Sci & Technol Dept Math Sci Daejeon South Korea Univ Montpellier CNRS LIRMM Montpellier France Univ Athens Dept Math Athens Greece Comp Technol Inst Press Diophantus Patras Greece

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.

关键词： fixed-parameter tractable algorithm Tree-cut width Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

From tree-decompositions to clique-width terms

引用

DISCRETE APPLIED MATHEMATICS 2018年 248卷 125-144页

作者： Courcelle, Bruno CNRS Labri F-33405 Talence France Bordeaux Univ F-33405 Talence France

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.

关键词： Tree-width Clique-width Sparse graph Planar graph Incidence graph fixed-parameter tractable algorithm

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for min-max multiway cut and list digraph homomorphism

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 86卷 191-206页

作者： Kim, Eun Jung Paul, Christophe Sau, Ignasi Thilikos, Dimitrios M. PSL Res Univ Univ Paris Dauphine CNRS LAMSADE Paris France CNRS LIRMM Montpellier France Univ Athens Dept Math Athens Greece Comp Technol Inst & Press Diophantus Patras Greece

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.

关键词： parameterized complexity fixed-parameter tractable algorithm Multiway Cut Digraph homomorphism

来源：评论

学校读者我要写书评

暂无评论

An FPT 2-Approximation for Tree-cut Decomposition 13th

An FPT 2-Approximation for Tree-cut Decomposition

引用

13th International Workshop on Approximation and Online algorithms (WAOA)

作者： Kim, Eunjung Oum, Sang-il Paul, Christophe Sau, Ignasi Thilikos, Dimitrios M. CNRS LAMSADE Paris France Korea Adv Inst Sci & Technol Dept Math Sci Daejeon South Korea Univ Montpellier CNRS LIRMM F-34059 Montpellier France Univ Athens Dept Math Athens Greece Comp Technol Inst Press Diophantus Patras Greece

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.

关键词： fixed-parameter tractable algorithm Tree-cut width Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Imbalance is fixed parameter tractable

引用

INFORMATION PROCESSING LETTERS 2013年第19-21期113卷 714-718页

作者： Lokshtanov, Daniel Misra, Neeldhara Saurabh, Saket Univ Calif San Diego San Diego CA 92103 USA Inst Math Sci Chennai 600113 Tamil Nadu India

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 fixed parameter tractable 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.

关键词： algorithms parameterized complexity Imbalance fixed-parameter tractable algorithm Graph layout problems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：