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

Group control for procedural rules:parameterized complexity and consecutive domains

Frontiers of Computer Science 2024年第3期18卷 133-141页

作者： Yongjie YANG Dinko DIMITROV Chair of Economic Theory Saarland UniversitySaarbrücken 66123Germany

We consider GROUP CONTROL BY ADDING INDIVIDUALS(GCAI)in the setting of group identification for two procedural rules-the consensus-start-respecting rule and the liberal-start-respecting *** is known that GCAI for both rules are NP-hard,but whether they are fixed-parameter tractable with respect to the number of distinguished individuals remained *** resolve both open problems in the *** addition,we strengthen the NP-hardness of GCAI by showing that,with respect to the natural parameter the number of added individuals,GCAI for both rules are W[2]-***,the W[2]-hardness for the liberal-startrespecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones ***,for the consensus-startrespecting rule,the problem becomes polynomial-time solvable in this special *** also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property,and show that under this restriction GCAI for both rules turn out to be polynomial-time *** reductions for showing W[2]-hardness also imply several algorithmic lowerbounds.

关键词： group control by adding individuals group identification parameterized complexity consecutive ones property FPT W[2]-hard

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Connected Even/Odd Subgraph Problems

Parameterized Complexity of Connected Even/Odd Subgraph Prob...

引用

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

作者： Fomin, Fedor V. Golovach, Petr A. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Sci Labs Durham DH1 3LE England

ISBN: (纸本)9783939897354

Cai and Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs. For a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about a connected k-EDGE subgraph with all vertices of odd degrees, the problem known as k-Edge CONNECTED ODD SUBGRAPH;and a connected k-vertex induced subgraph with all vertices of even degrees, the problem known as k-VERTEX EULERIAN SUBGRAPH. We resolve both open problems and thus complete the characterization of even/odd subgraph problems from parameterized complexity perspective. We show that k-EDGE CONNECTED ODD SUBGRAPH is FPT and that k-VERTEX EULERIAN SUBGRAPH IS W[1]-hard. Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges.

关键词： parameterized complexity Euler graph even graph odd graph treewidth

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of the maximum independent set problem and the speed of hereditary properties

引用

Electronic Notes in Discrete Mathematics 2009年 34卷 127-131页

作者： Lozin, Vadim V. DIMAP Mathematics Institute University of Warwick Coventry United Kingdom

For a hereditary class X, the number Xn of n-vertex graphs in X (also known as the speed of X) satisfies limn → ∞ frac(log2 Xn, ((n;2))) = 1 - frac(1, k (X)) where k (X) is a natural number called the index of the c... 详细信息

For a hereditary class X, the number X_n of n-vertex graphs in X (also known as the speed of X) satisfies lim_{n → ∞} frac(log₂ X_n, ((n;2))) = 1 - frac(1, k (X)) where k (X) is a natural number called the index of the class. Each class X of index k > 1 can be approximated by a minimal class of the same index. In this paper, we use Ramsey theory to show that the maximum independent set problem is fixed-parameter tractable in all minimal classes of index k for all values of k. © 2009 Elsevier B.V. All rights reserved.

关键词： Hereditary properties parameterized complexity Ramsey Theory

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of multiple-interval graph problems

引用

THEORETICAL COMPUTER SCIENCE 2009年第1期410卷 53-61页

作者： Fellows, Michael R. Hermelin, Danny Rosamond, Frances Vialette, Stephane Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Univ Newcastle Callaghan NSW 2308 Australia Univ Paris Sud Fac Sci Orsay CNRS LRIUMR 8623 F-91405 Orsay France

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we Study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k-INDEPENDENT SET, k-DOMINATING SET, and k-CLIQUE, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k-CLIQUE is in FPT, while k-INDEPENDENT SET and k-DOMINATING SET are both W[1]-hard. We also prove that k-INDEPENDENT DOMINATING SET, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k-MULTICOLORED CLIQUE problem, a variant of k-CLIQUE. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Multiple intervals Independent set Dominating set Clique W-hardness parameterized complexity Multicolored clique

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Lineal Topologies (Depth-first Spanning Trees) with Many or Few Leaves

引用

Journal of Computer and System Sciences 2025年

作者： Benjamin Bergougnoux Nello Blaser Michael Fellows Petr Golovach Frances Rosamond Emmanuel Sam Institute of Informatics University of Warsaw Poland Department of Informatics University of Bergen Norway Department of Computer Science and Mathematics Lebanese American University Beirut Lebanon

This paper considers four problems with possible applications in network design: Given a graph G with | G | = n and an integer k ≥ 0 , does G have a DFS tree with (i) ≤ k leaves, (ii) ≥ k leaves, (iii) ≤ n − k leaves, and (iv) ≥ n − k leaves? We show that all four problems are NP-hard. When parameterized by k , we prove that while (i) is para-NP-hard and (ii) is W[1]-hard, both (iii) and (iv) admit polynomial kernels with O ( k 3 ) vertices, implying FPT algorithms running in k O ( k ) ⋅ n O ( 1 ) time. Our polynomial kernels are based on a O ( k ) -sized vertex cover structure associated with the solution of these problems. As a byproduct, we obtain polynomial kernels for these problems parameterized by the vertex cover number of the input graph.

关键词： DFS Tree Spanning Tree Kernelization parameterized complexity Vertex Cover

来源：评论

学校读者我要写书评

暂无评论

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and parameterized complexity

引用

ALGORITHMICA 2018年第7期80卷 2160-2180页

作者： Bodlaender, Hans L. Ono, Hirotaka Otachi, Yota Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Univ Technol Eindhoven Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands Nagoya Univ Grad Sch Informat Chikusa Ku Furo Cho Nagoya Aichi 4648601 Japan Kumamoto Univ Fac Adv Sci & Technol Chuo Ku 2-39-1 Kurokami Kumamoto 8608555 Japan

The problem MAX W-LIGHT (MAX W-HEAVY) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, MAX 0- LIGHT is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MAX W-HEAVY can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MAX W-LIGHT, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54-87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

关键词： Orientation Graph class Width parameter parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

ON THE parameterized complexity OF COUNTING SMALL-SIZED MINIMUM (S,T)-CUTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2023年第2期37卷 964-996页

作者： Berge, Pierre Bouaziz, Wassim Rimmel, Arpad Tomasik, Joanna Univ Paris IRIF CNRS F-75013 Paris France Univ Paris Saclay CentraleSupe F-91190 Gif Sur Yvette France Univ Paris Scalay LISN CentraleSupelec F-91400 Orsay France

The counting of minimum edge (S, T)-cuts in undirected graphs, parameterized by the size p of these cuts, is FPT. The best performance in the literature is O\ast(2O(p2)). We treat a more general problem of counting minimum (S, T)-cuts composed of vertices instead of edges. We propose an FPT algorithm with running time O\ast(2O(p log p)). As it may be applied to the edge version as well, we improve the time complexity of the minimum edge (S, T )-cuts counting.

关键词： parameterized complexity counting problems minimum (S T)-cuts

来源：评论

学校读者我要写书评

暂无评论

Approximate inference in Bayesian networks: parameterized complexity results

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2018年 93卷 119-131页

作者： Kwisthout, Johan Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav Montessorilaan 3 NL-6525 HR Nijmegen Netherlands

Computing posterior and marginal probabilities constitutes the backbone of almost all inferences in Bayesian networks. These computations are known to be intractable in general, both to compute exactly and to approximate (e.g., by sampling algorithms). While it is well known under what constraints exact computation can be rendered tractable (viz., bounding tree-width of the moralized network and bounding the cardinality of the variables) it is less known under what constraints approximate Bayesian inference can be tractable. Here, we extend the existing formal framework of fixed-error randomized tractability (a randomized analogue of fixed-parameter tractability), and use it to address this problem, both by re-interpreting known results from the literature and by providing some additional new results, including results on fixed parameter tractable de-randomization of approximate inference. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Approximate inference Sampling Bayesian networks parameterized complexity Stochastic algorithms De-randomization

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2003年第4期67卷 757-771页

作者： Pietrzak, K McGill Univ Computat Biol Lab Montreal PQ Canada

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1] = FPT, this rules out the existence of algorithms with time complexity of O(f(k)n(alpha)) for those problems. Here n is the size of the problem instance, alpha is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences. (C) 2003 Elsevier Inc. All rights reserved.

关键词： parameterized complexity longest common subsequence shortest common supersequence multiple sequence alignment

来源：评论

学校读者我要写书评

暂无评论

Machine-based methods in parameterized complexity theory

引用

THEORETICAL COMPUTER SCIENCE 2005年第2-3期339卷 167-199页

作者： Chen, YJ Flum, J Grohe, M Humboldt Univ Inst Informat D-10099 Berlin Germany Univ Freiburg Abt Math Log D-79104 Freiburg Germany

We give machine characterizations of most parameterized complexity classes, in particular, of W[P], of the classes of the W-hierarchy, and of the A-hierarchy. For example, we characterize W[P] as the class of all parameterized problems decidable by a nondeterministic fixed-parameter tractable algorithm whose number of nondeterministic steps is bounded in terms of the parameter. The machine characterizations suggest the introduction of a hierarchy W-func between the W- and the A-hierarchy. We study the basic properties of this hierarchy. (c) 2005 Elsevier B.V. All rights reserved.

关键词： parameterized complexity machine characterizations complexity classes

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：