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

Linear Time algorithms for Finding a Dominating Set of fixed Size in Degenerated Graphs

ALGORITHMICA 2009年第4期54卷 544-556页

作者： Alon, Noga Gutner, Shai Tel Aviv Univ Sch Math IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a k (O(dk)) n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain K (h) as a topological minor, we give an improved algorithm for the problem with running time (O(h)) (hk) n. For graphs which are K (h) -minor-free, the running time is further reduced to (O(log h)) (hk/2) n. fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(nlog n) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs.

关键词： H-minor-free graphs Degenerated graphs Dominating set problem Finding an induced cycle fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving hard stable matching problems involving groups of similar agents

引用

THEORETICAL COMPUTER SCIENCE 2020年 844卷 171-194页

作者： Meeks, Kitty Rastegari, Baharak Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland Univ Southampton Dept Elect & Comp Sci Southampton Hants England

Many important stable matching problems are known to be NP-hard, even when strong restrictions are placed on the input. In this paper we seek to identify structural properties of instances of stable matching problems which will allow us to design efficient algorithms using elementary techniques. We focus on the setting in which all agents involved in some matching problem can be partitioned into k different types, where the type of an agent determines his or her preferences, and agents have preferences over types (which may be refined by more detailed preferences within a single type). This situation would arise in practice if agents form preferences solely based on some small collection of agents' attributes. We also consider a generalisation in which each agent may consider some small collection of other agents to be exceptional, and rank these in a way that is not consistent with their types;this could happen in practice if agents have prior contact with a small number of candidates. We show that (for the case without exceptions), several well-studied NP-hard stable matching problems including MAX SMTI (that of finding the maximum cardinality stable matching in an instance of stable marriage with ties and incomplete lists) belong to the parameterised complexity class FPT when parameterised by the number of different types of agents needed to describe the instance. For MAX SMTI this tractability result can be extended to the setting in which each agent promotes at most one "exceptional" candidate to the top of his/her list (when preferences within types are not refined), but the problem remains NP-hard if preference lists can contain two or more exceptions and the exceptional candidates can be placed anywhere in the preference lists, even if the number of types is bounded by a constant. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Stable matchings Stable marriage problem Stable roommate problem NP-hard problems parameterized complexity fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

Beyond Max-Cut: λ-extendible properties parameterized above the Poljak-Turzik bound

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2014年第7期80卷 1384-1403页

作者： Mnich, Matthias Philip, Geevarghese Saurabh, Saket Suchy, Ondrej Max Planck Inst Informat D-66123 Saarbrucken Germany Inst Math Sci Chennai 600113 Tamil Nadu India Czech Tech Univ CR-16635 Prague Czech Republic

We define strong lambda-extendibility as a variant of the notion of lambda-extendible properties of graphs (Poljak and Turzik, Discrete Mathematics, 1986). We show that the parameterized APT(Pi) problem - given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that H is an element of Pi and H has at least [GRAPHICS] edges - is fixed-parameter tractable (FPT) for all 0 < lambda < 1, for all strongly lambda-extendible graph properties Pi for which the APT(Pi) problem is FPT on graphs which are 0(k) vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on MAX-CUT parameterized above the Edwards-Erdos bound, and yield FPT algorithms for several graph problems parameterized above lower bounds. (C) 2014 Elsevier Inc. All rights reserved.

关键词： algorithms and data structures fixed-parameter tractable algorithms Above-guarantee parameterization MAX-CUT lambda-extendible properties

来源：评论

学校读者我要写书评

暂无评论

Backdoors to planning

引用

ARTIFICIAL INTELLIGENCE 2019年 269卷 49-75页

作者： Kronegger, Martin Ordyniak, Sebastian Pfandler, Andreas Johannes Kepler Univ Linz Linz Austria TU Wien Vienna Austria Univ Sheffield Sheffield S Yorkshire England Univ Siegen Siegen Germany

Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms for hard problems in Al and beyond. Despite their success, backdoors have not been used for planning, a central problem in Al that has a high computational complexity. In this work, we introduce two notions of backdoors building upon the causal graph. We analyze the complexity of finding a small backdoor (detection) and using the backdoor to solve the problem (evaluation) in the light of planning with (un)bounded plan length/domain of the variables. For each setting we present either an fpt-result or rule out the existence thereof by showing parameterized intractability. For several interesting cases we achieve the most desirable outcome: detection and evaluation are fpt. In addition, we explore the power of polynomial preprocessing for all fpt-results, i.e., we investigate whether polynomial kernels exist. We show that for the detection problems, polynomial kernels exist whereas we rule out the existence of polynomial kernels for the evaluation problems. (C) 2018 Published by Elsevier B.V

关键词： Planning Backdoors Causal graph fixed-parameter tractable algorithms (parameterized) complexity

来源：评论

学校读者我要写书评

暂无评论

A Polynomial-Time Algorithm to Compute Turaev-Viro Invariants TV4,q of 3-Manifolds with Bounded First Betti Number

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2020年第5期20卷 1013-1034页

作者： Maria, Clement Spreer, Jonathan INRIA Sophia Antipolis Mediterranee Valbonne France Univ Sydney Sydney NSW 2006 Australia

In this article, we introduce a fixed-parameter tractable algorithm for computing the Turaev-Viro invariants TV4, q, using the first Betti number, i.e. the dimension of the first homology group of the manifold with Z(2)-coefficients, as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV4, q is known to be #P-hard in general;using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the family of 3-manifolds with first Z(2)-homology group of bounded dimension. Our algorithm is easy to implement, and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3-manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets, we are able to almost double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV4, q to be added to the short list of standard properties (such as orientability, connectedness and Betti numbers) that can be computed ad hoc when first investigating an unknown triangulation.

关键词： fixed-parameter tractable algorithms Turaev-Viro invariants Triangulations of 3-manifolds (Integral)homology (Generalised)normal surfaces Discrete algorithms

来源：评论

学校读者我要写书评

暂无评论

Euclidean TSP in Narrow Strips

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2024年第4期71卷 1456-1506页

作者： Alkema, Henk de Berg, Mark van der Hofstad, Remco Kisfaludi-Bak, Sandor TU Eindhoven Dept Math & Comp Sci Eindhoven Netherlands Aalto Univ Espoo Finland

We investigate how the complexity of Euclidean TSP for point sets P inside the strip (-infinity,+infinity)x[0,delta] depends on the strip width delta . - We obtain two main *** the case where the points have distinct integer -coordinates, we prove that a shortest bitonic tour (which can be computed in O(nlog(2)n) time using an existing algorithm) is guaranteed to be a shortest tour overall when delta <= 2 root 2 , a bound which is best possible. - We present an algorithm that is fixed-parameter tractable with respect to delta . Our algorithm has running time 2(O(root delta)n)+O(delta(2)n(2)) for sparse point sets, where each 1x delta rectangle inside the strip contains (1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0,n]x[0,delta] , it has an expected running time of 2(O(root delta)n) . These results generalise to point sets inside a hypercylinder of width delta . In this case, the factors 2(O(root delta)) become 2(O(delta 1-1/d)) .

关键词： Computational geometry Euclidean TSP Bitonic TSP fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

Infrared: a declarative tree decomposition-powered framework for bioinformatics

引用

algorithms FOR MOLECULAR BIOLOGY 2024年第1期19卷 1-29页

作者： Yao, Hua-Ting Marchand, Bertrand Berkemer, Sarah J. Ponty, Yann Will, Sebastian Ecole Polytech CNRS Inst Polytech Paris LIXUMR 7161 Palaiseau France Univ Vienna Dept Theoret Chem Vienna Austria McGill Univ Sch Comp Sci Montreal PQ Canada Tokyo Inst Technol Earth Life Sci Inst Tokyo Japan

MotivationMany bioinformatics problems can be approached as optimization or controlled sampling tasks, and solved exactly and efficiently using Dynamic Programming (DP). However, such exact methods are typically tailored towards specific settings, complex to develop, and hard to implement and adapt to problem *** introduce the Infrared framework to overcome such hindrances for a large class of problems. Its underlying paradigm is tailored toward problems that can be declaratively formalized as sparse feature networks, a generalization of constraint networks. Classic Boolean constraints specify a search space, consisting of putative solutions whose evaluation is performed through a combination of features. Problems are then solved using generic cluster tree elimination algorithms over a tree decomposition of the feature network. Their overall complexities are linear on the number of variables, and only exponential in the treewidth of the feature network. For sparse feature networks, associated with low to moderate treewidths, these algorithms allow to find optimal solutions, or generate controlled samples, with practical empirical *** these methods, the Infrared software allows Python programmers to rapidly develop exact optimization and sampling applications based on a tree decomposition-based efficient processing. Instead of directly coding specialized algorithms, problems are declaratively modeled as sets of variables over finite domains, whose dependencies are captured by constraints and functions. Such models are then automatically solved by generic DP algorithms. To illustrate the applicability of Infrared in bioinformatics and guide new users, we model and discuss variants of bioinformatics applications. We provide reimplementations and extensions of methods for RNA design, RNA sequence-structure alignment, parsimony-driven inference of ancestral traits in phylogenetic trees/networks, and design of coding sequences.

关键词： Bioinformatics fixed-parameter tractable algorithms Tree decomposition Boltzmann sampling Network phylogeny RNA sequence design RNA alignment Pseudoknots

来源：评论

学校读者我要写书评

暂无评论

A single-exponential FPT algorithm for the K₄-MINOR COVER problem

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第1期81卷 186-207页

作者： Kim, Eun Jung Paul, Christophe Philip, Geevarghese CNRS LAMSADE Paris France CNRS LIRMM Montpellier France MPII Saarbrucken Germany

Given a graph G and a parameter k is an element of N, the parameterized K-4-MINOR COVER problem asks whether at most k vertices can be deleted to turn G into a K-4-minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, VERTEX COVER and FEEDBACK VERTEX SET, Which Can also be expressed as TREEWIDTH-t VERTEX DELETION problems: t = 0 for VERTEX COVER and t = 1 for FEEDBACK VERTEX SET. While single-exponential FPT algorithms, i.e. running in 2(O(k)).n(O(1)) co time, are known for these two latter problems, it was open whether the K-4-MINOR COVER problem could be solved in single-exponential EFT time. This paper answers this question in the affirmative. Observe that it is known to be unlikely that TREEWIDTH-t VERTEX DELETION can be solved in time 2(O(k)).n(O(1)). (c) 2014 Published by Elsevier Inc.

关键词： TREEWIDTH-2 DELETION fixed-parameter tractable algorithms K-4-MINOR COVER

来源：评论

学校读者我要写书评

暂无评论

On parameterized Independent Feedback Vertex Set

引用

THEORETICAL COMPUTER SCIENCE 2012年 461卷 65-75页

作者： Misra, Neeldhara Philip, Geevarghese Raman, Venkatesh Saurabh, Saket Inst Math Sci Madras 600113 Tamil Nadu India

We investigate a generalization of the classical FEEDBACK VERTEX SET (FVS) problem from the point of view of parameterized algorithms. INDEPENDENT FEEDBACK VERTEX SET (IFVS) is the "independent" variant of the FVS problem and is defined as follows: given a graph G and an integer k, decide whether there exists F subset of V (G), vertical bar F vertical bar <= k, such that G[V(G)\F] is a forest and G[F] is an independent set;the parameter is k. Note that the similarly parameterized version of the FVS problem - where there is no restriction on the graph G[F] - has been extensively studied in the literature. The connected variant CFVS - where G[F] is required to be connected - has received some attention as well. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in O(5(k)n(O(1))) time, where n is the number of vertices in the input graph G, and obtain a cubic (O(k(3))) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless CoNP subset of NP/Poly. (c) 2012 Elsevier B.V. All rights reserved.

关键词： fixed-parameter tractable algorithms Polynomial kernels Feedback Vertex Set problems

来源：评论

学校读者我要写书评

暂无评论

Diverse Collections in Matroids and Graphs 38

Diverse Collections in Matroids and Graphs

引用

38th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fomin, Fedor, V Golovach, Petr A. Panolan, Fahad Philip, Geevarghese Saurabh, Saket Univ Bergen Bergen Norway IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Chennai Math Inst Chennai Tamil Nadu India UMI ReLaX Chennai Tamil Nadu India Inst Math Sci4 Chennai Tamil Nadu India

ISBN: (纸本)9783959771801

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the WEIGHTED DIVERSE BASES problem consists of a matroid M, a weight function omega : E(M) -> N, and integers k >= 1, d >= 0. The task is to decide if there is a collection of k bases B-1, ... , B-k of M such that the weight of the symmetric difference of any pair of these bases is at least d. This is a diverse variant of the classical matroid base packing problem. The input to the WEIGHTED DIVERSE COMMON INDEPENDENT SETS problem consists of two matroids M-1, M-2 defined on the same ground set E, a weight function omega : E -> N, and integers k >= 1, d >= 0. The task is to decide if there is a collection of k common independent sets I-1, ... , I-k of M-1 and M-2 such that the weight of the symmetric difference of any pair of these sets is at least d. This is motivated by the classical weighted matroid intersection problem. The input to the DIVERSE PERFECT MATCHINGS problem consists of a graph G and integers k >= 1, d >= 0. The task is to decide if G contains k perfect matchings M-1, ... , M-k such that the symmetric difference of any two of these matchings is at least d. The underlying problem of finding one solution (basis, common independent set, or perfect matching) is known to be doable in polynomial time for each of these problems, and DIVERSE PERFECT MATCHINGS is known to be NP-hard for k = 2. We show that WEIGHTED DIVERSE BASES and WEIGHTED DIVERSE COMMON INDEPENDENT SETS are both NP-hard. We show also that DIVERSE PERFECT MATCHINGS cannot be solved in polynomial time (unless P = NP) even for the case d = 1. We derive fixed-parameter tractable (FPT) algorithms for all three problems with (k, d) as the parameter. The above results on matroids are derived under the assumption that the input matroids are given as independence oracles. For WEIGHTED DIVERSE BASES

关键词： Matroids Diverse solutions fixed-parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：