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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Finding branch-decompositions and rank-decompositions

引用

SIAM JOURNAL ON COMPUTING 2008年第3期38卷 1012-1032页

作者： Hlineny, Petr Oum, Sang-Il Masaryk Univ Fac Informat Brno 60200 Czech Republic Korea Adv Inst Sci & Technol Dept Math Sci Taejon 305701 South Korea

We present a new algorithm that can output the rank-decomposition of width at most k of a graph if such exists. For that we use an algorithm that, for an input matroid represented over a fixed finite field, outputs its branch-decomposition of width at most k if such exists. This algorithm works also for partitioned matroids. Both of these algorithms are fixed-parameter tractable, that is, they run in time O(n(3)) where n is the number of vertices / elements of the input, for each constant value of k and any fixed finite field. The previous best algorithm for construction of a branch-decomposition or a rank-decomposition of optimal width due to Oum and Seymour [J. Combin. Theory Ser. B, 97 (2007), pp. 385 - 393] is not fixed-parameter tractable.

关键词： rank-width clique-width branch-width fixed-parameter tractable algorithm graph matroid

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 complexity of finding small degree-constrained subgraphs

引用

JOURNAL OF DISCRETE algorithmS 2012年第1期10卷 70-83页

作者： Amini, Omid Sau, Ignasi Saurabh, Saket ENS DMA CNRS Paris France LIRMM CNRS Montpellier France Inst Math Sci Madras Tamil Nadu India

In this article we study the parameterized complexity of problems consisting in finding degree-constrained subgraphs, taking as the parameter the number of vertices of the desired subgraph. Namely, given two positive integers d and k, we study the problem of finding a d-regular (induced or not) subgraph with at most k vertices and the problem of finding a subgraph with at most k vertices and of minimum degree at least d. The latter problem is a natural parameterization of the d-girth of a graph (the minimum order of an induced subgraph of minimum degree at least d). We first show that both problems are fixed-parameter intractable in general graphs. More precisely, we prove that the first problem is W[1]-hard using a reduction from MULTI-COLOR Clique. The hardness of the second problem (for the non-induced case) follows from an easy extension of an already known result. We then provide explicit fixed-parameter tractable (FPT) algorithms to solve these problems in graphs with bounded local treewidth and graphs with excluded minors, using a dynamic programming approach. Although these problems can be easily defined in first-order logic, hence by the results of Frick and Grohe (2001) [23] are FPT in graphs with bounded local treewidth and graphs with excluded minors, the dependence on k of our algorithms is considerably better than the one following from Frick and Grohe (2001) [23]. (C) 2011 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Degree-constrained subgraph fixed-parameter tractable algorithm W[1]-hardness Treewidth Dynamic programming Excluded minors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：