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

作者： Irena Schindler Gottfried Wilhelm Leibniz Universitat Hannover

学位级别：博士

parameterized complexity is a branch of a computational complexity. The pioneers of this new and promising research field are Downey and Fellows [ DF99 ]. They suggest to examine the structural properties of a given problem and restrict the instance by a parameter. In this thesis we investigate the parameterized complexity of various problems in default logic and in temporal logics. In the first section of Chapter 3 we introduce a dynamic programming algorithm which decides whether a given default theory has a consistent stable extension in fpt-time and enumerates all generating defaults that lead to a stable extension with a pre-computation step that is linear in the input theory and triple exponential in the tree-width followed by a linear delay to output solutions. In the second part of this chapter we lift the notion of backdoors to the field of default logics. We consider two problems, first we are interested to detect a backdoor and then to evaluate it for the target formulae classes HORN, KROM, POSITIVE-UNIT and MONOTONE. In Chapter 4, we investigate the parameterized complexity of problems in various tem- poral logics. In the first section we introduce several graph-like structures for formula representation and the corresponding notion of tree-width and path-width. To obtain the fixed parameter tractability of different fragments, we generalize the prominent Courcelle's Theorem to work for infinite signatures. In this section, we also consider Boolean operator fragments in the sense of Post's lattice. In the second part of Chapter 4 we introduce the notion of backdoors for the glob- ally fragment of linear temporal logic. Again, our problems of interest are to detect a backdoor and to evaluate it, this time, for the target formulae classes HORN and KROM.

关键词： parameterized complexity default logic temporal logic backdoor Post's Lattice tree-and pathwidth temporal depth

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of d-Hitting Set with Quotas 47th

Parameterized Complexity of <i>d</i>-Hitting Set with Quotas

引用

47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Gupta, Sushmita Jain, Pallavi Petety, Aditya Singh, Sagar HBNI Inst Math Sci IMSc Jodhpur Rajasthan India Indian Inst Technol Jodhpur Jodhpur Rajasthan India HBNI Natl Inst Sci Educ & Res NISER Jodhpur Rajasthan India

ISBN: (纸本)9783030677305;9783030677312

In this paper we study a variant of the classic d-HITTING SET problem with lower and upper capacity constraints, say A and B, respectively. The input to the problem consists of a universe U, a set family, J, of sets over U, where each set in the family is of size at most d, a non-negative integer k;and additionally two functions alpha: J -> {1,..., A} and beta : J -> {1,..., B}. The goal is to decide if there exists a hitting set of size at most k such that for every set S in the family J, the solution contains at least alpha(S) elements and at most beta(S) elements from S. We call this the (A, B)-MULTI d-HITTING SET problem. We study the problem in the realm of parameterized complexity. We show that (A, B)-MULTI d-HITTING SET can be solved in O-star (d(k)) time. For the special case when d = 3 and d = 4, we have an improved bound of O-star (2.2738(k)) and O-star (3.562(k)), respectively. The former matches the running time of the classical 3-HITTING SET problem. Furthermore, we show that if we do not have an upper bound constraint and the lower bound constraint is same for all the sets in the family, say A > 1, then the problem can be solved even faster than d-HITTING SET. We next investigate some graph-theoretic problems which can be thought of as an implicit d-HITTING SET problem. In particular, we study (A, B)-Multi Vertex Cover and (A, B)-MULTI FEEDBACK VERTEX SET IN TOURNAMENTS. In (A, B)-MULTI VERTEX COVER, we are given a graph G and a non-negative integer k, the goal is to find a subset S subset of V (G) of size at most k such that for every edge in G, S contains at least A and at most B of its endpoints. Analogously, we can define (A, B)-MULTI FEEDBACK VERTEX SET IN TOURNAMENTS. We show that unlike VERTEX COVER, which is same as (1, 2)-MULTI VERTEX COVER, (1, 1)-MULTI VERTEX COVER is polynomial-time solvable. Furthermore, unlike Feedback Vertex Set in Tournaments, (A, B)-MULTI FEEDBACK VERTEX SET IN TOURNAMENTS can be solved in polynomial time.

关键词： parameterized complexity Kernelization Multi hitting set

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of generalized domination problems

Parameterized complexity of generalized domination problems

引用

4th Workshop on Graph Classes, Optimization, and Width Parameters (GROW)

作者： Golovach, Petr A. Kratochvil, Jan Suchy, Ondrej Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci ITI CR-11800 Prague Czech Republic Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

Given two sets a. p of non-negative integers, a set S of vertices of a graph G is (a. p)dominating if |S boolean AND N(v)| is an element of sigma for every vertex v is an element of S. and |S boolean AND N(v)| is an element of rho for every v S. This concept, introduced by Telle in 1990's, generalizes and unifies several variants of graph domination studied separately before. We study the parameterized complexity of (sigma, rho)-domination in this general setting. Among other results, we show that the existence of a (sigma, rho)-dominating set of size k (and at most k) are W[1]-complete problems (when parameterized by k) for any pair of finite sets a and p. We further present results on dual parameterization by n - k, and results on certain infinite sets (in particular for a. p being the sets of even and odd integers). (C) 2010 Elsevier B.V. All rights reserved.

关键词： Generalized domination parameterized complexity Even set Odd set

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Defensive and Offensive Alliances in Graphs 17th

Parameterized Complexity of Defensive and Offensive Alliance...

引用

17th International Conference on Distributed Computing and Intelligent Technology

作者： Gaikwad, Ajinkya Maity, Soumen Tripathi, Shuvam Kant Indian Inst Sci Educ & Res Pune Maharashtra India

ISBN: (纸本)9783030656201;9783030656218

In this paper we study the problem of finding small defensive and offensive alliances in a simple graph. Given a graph G = (V, E) and a subset S subset of V (G), we denote by d(S)(v) the degree of a vertex v is an element of V in G[S], the subgraph of G induced by S. A non-empty set S subset of V is a defensive alliance in G = (V, E) if d(S)(v)+ 1 >= d(Sc) (v) for all v is an element of S. A non-empty set S subset of V is an offensive alliance in G if d(S)(v) = d(Sc) (v)+ 1 for all v is an element of N(S). It is known that the problems of finding small defensive and offensive alliances are NP-complete. We enhance our understanding of the problems from the viewpoint of parameterized complexity by showing that (1) the problems are FPT when parameterized by neighbourhood diversity of the input graph, (2) the offensive alliance problem is FPT when parameterized by domino treewidth of the input graph, and (3) the defensive and offensive alliance problems are polynomial time solvable for graphs with bounded treewidth.

关键词： Defensive and offensive alliance parameterized complexity FPT W-hard Treewidth

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Broadcasting in Graphs 49th

Parameterized Complexity of Broadcasting in Graphs

引用

49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Fomin, Fedor V. Fraigniaud, Pierre Golovach, Petr A. Univ Bergen Dept Informat Bergen Norway Univ prime Paris Cite Inst Rech Informat Fondamentale Paris France CNRS Paris France

ISBN: (纸本)9783031433795;9783031433801

The task of the broadcast problem is, given a graph G and a source vertex s, to compute the minimum number of rounds required to disseminate a piece of information from s to all vertices in the graph. It is assumed that, at each round, an informed vertex can transmit the information to at most one of its neighbors. The broadcast problem is known to be NP-hard. We show that the problem is FPT when parametrized by the size k of a feedback edge set, or by the size k of a vertex cover, or by k = n- t, where t is the input deadline for the broadcast protocol to complete.

关键词： broadcasting telephone model parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of constraint satisfaction problems

Parameterized complexity of constraint satisfaction problems

引用

19th IEEE Annual Conference on Computational complexity

作者： Marx, D Budapest Univ Technol & Econ Dept Comp Sci & Informat Theory H-1521 Budapest Hungary

ISBN: (纸本)0769521207

We prove a parameterized analog of Schaefer's Dichotomy Theorem: we show that for every finite boolean constraint family F, deciding whether a formula containing constraints from F has a satisfying assignment of weight exactly k is either fixed-parameter tractable (FPT) or W[1]-complete. We give a simple characterization of those constraints that make the problem fixed-parameter tractable. The special cases when the formula is restricted to be bounded occurrence, bounded treewidth, or planar are also considered: it turns out that in these cases the problem is in FPT for every constraint family F.

关键词： constraint satisfaction weighted satisfiability parameterized complexity weak separability

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Committee Elections with Dichotomous and Trichotomous Votes 18

Parameterized Complexity of Committee Elections with Dichoto...

引用

18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

作者： Zhou, Aizhong Yang, Yongjie Guo, Jiong Shandong Univ Sch Comp Sci & Technol Jinan Shandong Peoples R China Cent South Univ Changsha Hunan Peoples R China

ISBN: (纸本)9781450363099

We study the winner determination problem for three prevalent committee election rules: Chamberlin-Courant Approval Voting (CCA), Proportional Approval Voting (PAV), and Satisfaction Approval Voting (SAV). Axiomatic and algorithmic studies of elections under these rules have been conducted recently. It is known that the winner determination problem is NP-hard for CCA and PAV and polynomial-time solvable for SAV, if the input votes are dichotomous. Moreover, parameterized complexity of the two NP-hard cases has been examined with respect to some natural parameters such as the number of candidates or the number of votes. In this paper, we extend the above studies to committee elections with trichotomous votes and identify cases, where trichotomous votes lead to an increase of parameterized complexity. We also consider the maximin (or egalitarian) variations of the rules, where the minimum satisfaction of the voters is maximized.

关键词： Committee elections parameterized complexity maximin

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Resilience Decision for Database Debugging 19th

Parameterized Complexity of Resilience Decision for Database...

引用

19th International Conference on Formal Engineering Methods (ICFEM)

作者： Miao, Dongjing Cai, Zhipeng Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Harbin Engn Univ Coll Comp Sci & Technol Harbin 150001 Heilongjiang Peoples R China

ISBN: (纸本)9783319686905;9783319686899

Resilience decision problem plays a fundamental and important role in database debugging, query explanation and error tracing. Resilience decision problem is defined on a database d, given a boolean query q which is true initially, and a constant k > 0, it is to decide if there is a fact set res of size no more than k such that query q becomes false after deleting all facts in res. Previous results showed it is NP-hard in many cases. However, we revisit this decision problem, in the light of the recent parametric refinement of complexity theory, provide some new results including negative and positive ones. We show that, there are still some cases intractable if only consider the query size or variable numbers as the parameter.

关键词： Resilience Database parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity Classes Defined by Threshold Circuits: Using Sorting Networks to Show Collapses with W-hierarchy Classes 15th

Parameterized Complexity Classes Defined by Threshold Circui...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Paranhos, Raffael M. Nascimento Silva, Janio Carlos Souza, Ueverton S. Ochi, Luiz Satoru Univ Fed Fluminense Inst Comp Niteroi RJ Brazil Inst Fed Tocantins Campus Porto Nacl Porto Nacl TO Brazil

ISBN: (纸本)9783030926816;9783030926809

The main complexity classes of the parameterized Intractability Theory are based on weighted Boolean circuit satisfiability problems and organized into a hierarchy so-called W-hierarchy. The W-hierarchy enables fine-grained complexity analyses of parameterized problems that are unlikely to belong to the FPT class. In this paper, we introduce the Th-hierarchy, a natural generalization of the W-hierarchy defined by weighted threshold circuit satisfiability problems. Investigating the relationship between Th-hierarchy and W-hierarchy, we discuss the complexity of transforming Threshold circuits into Boolean circuits, and observe that sorting networks are powerful tools to handle such transformations. First, we show that these hierarchies collapse at the last level (W[P] = Th[P]). After that, we present a time complexity analysis of an AKS sorting network construction, which supports some of our results. Finally, we prove that Th[t] subset of W[SAT] for every t is an element of N.

关键词： Threshold circuits AKS sorting network parameterized complexity W-hierarchy

来源：评论

学校读者我要写书评

暂无评论

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-hard

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：