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

International Conference on Autonomous Agents and Multiagent Systems

作者： Ulle Endriss Ronald de Haan Stefan Szeider ILLC University of Amsterdam Technische Universitat Wien

ISBN: (纸本)9781450337694

Many problems arising in computational social choice are of high computational complexity, and some are located at higher levels of the Polynomial Hierarchy. We argue that a parameterized complexity analysis provides valuable insight into the factors contributing to the complexity of these problems, and can lead to practically useful algorithms. As a case study, we consider the problem of agenda safety for the majority rule in judgment aggregation, consider several natural parameters for this problem, and determine the parameterized complexity for each of these. Our analysis is aimed at obtaining fixed-parameter tractable (fpt) algorithms that use a small number of calls to a SAT solver. We identify several positive results, including several results where the problem can be fpt-reduced to a single SAT instance. In addition, we identify several negative results. We hope that this work may help initiate a structured parameterized complexity investigation of problems arising in the field of computational social choice that are located at higher levels of the Polynomial Hierarchy.

关键词： Judgment Aggregation Agenda Safety complexity Theory parameterized complexity Treewidth complexity theory parameterization Judgment complexity Analysis complexity SEMI-AUTOMATIC TRIM College Entrance Examination Board Scholastic Aptitude Test

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity and Kernelization of the Workflow Satisfiability Problem

引用

ACM TRANSACTIONS ON INFORMATION AND SYSTEM SECURITY 2013年第1期16卷 4-4页

作者： Crampton, Jason Gutin, Gregory Yeo, Anders Univ London Dept Math London WC1E 7HU England Univ London Dept Comp Sci London WC1E 7HU England Univ Johannesburg Dept Math Johannesburg South Africa

A workflow specification defines a set of steps and the order in which these steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of these steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications and for the construction of runtime reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li [2010] using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this article, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely accepted complexity-theoretical assumption holds.

关键词： Algorithms Security Theory Authorization constraints workflow satisfiability parameterized complexity kernelization

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of s-club cluster deletion problems

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期969卷

作者： Montecchiani, Fabrizio Ortali, Giacomo Piselli, Tommaso Tappini, Alessandra Univ Perugia Dept Engn Perugia Italy

We study the parameterized complexity of the s-CLUB CLUSTER EDGE DELETION (s-CLUB CLUSTER VERTEX DELETION) problem: Given a graph G and two integers s > 2 and k > 1, is it possible to remove at most k edges (vertices) from G such that each connected component of the resulting graph has diameter at most s? Both s-CLUB CLUSTER EDGE DELETION and s -CLUB CLUSTER VERTEX DELETION problems are known to be NP-hard already when s = 2. We prove that they admit a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph. The proof is based on a unified algorithm that solves the more general problem in which both edges and vertices can be removed from the input graph to obtain a set of disjoint components with bounded diameter. Our approach can also be exploited to solve a related problem, namely s-CLUB COVER, which asks whether it is possible to cover the vertices of a graph with at most d different s-clubs, for some fixed d > 1 and s > 2.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Cluster deletion problems parameterized complexity s-Club

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of manipulating Top Trading Cycles

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2022年第2期36卷 51-51页

作者： Phan, William Purcell, Christopher North Carolina State Univ Dept Econ Raleigh NC 27695 USA Univ West Bohemia Dept Math Plzen Czech Republic

We study the problem of exchange when agents are endowed with heterogeneous indivisible objects, and there is no money. In this setting, no rule satisfies Pareto-efficiency, individual rationality, and strategy-proof/less;there is no consensus in the literature on satisfactory second-best mechanisms. A natural generalization of the ubiquitous Top Trading Cycles (TTC) satisfies the first two properties on the lexicographic domain, rendering it manipulable. We characterize the computational complexity of manipulating this mechanism;we show that it is W[P]-hard by reduction from MONOTONE WEIGHTED CIR-CUIT SATISFIABILITY. We provide a matching upper bound for a wide range of preference domains. We further show that manipulation by groups (when parameterized by group size) is W[P]-hard. This provides support for TTC as a second-best mechanism. Lastly, our results are of independent interest to complexity theorists: there are few natural W[P]-complete problems and, as far as we are aware, this is the first such problem arising from the social sciences.

关键词： Top trading cycles parameterized complexity Manipulation

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2017年第3期18卷 21-21页

作者： De Haan, Ronald Kanj, Iyad Szeider, Stefan TU Wien Algorithms & Complex Grp Favoritenstr 9-11 A-1040 Vienna Austria Depaul Univ Sch Comp Chicago IL 60604 USA Depaul Univ Coll Comp & Digital Media 243 South Wabash Ave Chicago IL 60604 USA

In many practical settings it is useful to find a small unsatisfiable subset of a given unsatisfiable set of constraints. We study this problem from a parameterized complexity perspective, taking the size of the unsatisfiable subset as the natural parameter where the set of constraints is either (i) given a set of clauses, i.e., a formula in conjunctive normal Form (CNF), or (ii) as an instance of the Constraint Satisfaction Problem (CSP). In general, the problem is fixed-parameter intractable. For an instance of the propositional satisfiability problem (SAT), it was known to be W[1]-complete. We establish A[2]-completeness for CSP instances, where A[2]-hardness prevails already for the Boolean case. With these fixed-parameter intractability results for the general case in mind, we consider various restricted classes of inputs and draw a detailed complexity landscape. It turns out that often Boolean CSP and CNF formulas behave similarly, but we also identify notable exceptions to this rule. The main part of this article is dedicated to classes of inputs that are induced by Boolean constraint languages that Schaefer [1978] identified as the maximal constraint languages with a tractable satisfiability problem. We show that for the CSP setting, the problem of finding small unsatisfiable subsets remains fixed-parameter intractable for all Schaefer languages for which the problem is non-trivial. We show that this is also the case for CNF formulas with the exception of the class of bijunctive (Krom) formulas, which allows for an identification of a small unsatisfiable subset in polynomial time. In addition, we consider various restricted classes of inputs with bounds on the maximum number of times that a variable occurs (the degree), bounds on the arity of constraints, and bounds on the domain size. For the case of CNF formulas, we show that restricting the degree is enough to obtain fixed-parameter tractability, whereas for the case of CSP instances, one needs to restric

关键词： parameterized complexity constraint satisfaction unsatisfiable subsets CNF formulas backbones

来源：评论

学校读者我要写书评

暂无评论

A survey on the parameterized complexity of reconfiguration problems

引用

COMPUTER SCIENCE REVIEW 2024年 53卷

作者： Bousquet, Nicolas Mouawad, Amer E. Nishimura, Naomi Siebertz, Sebastian Univ Claude Bernard Lyon 1 Lyon France Amer Univ Beirut Beirut Lebanon Univ Waterloo Waterloo ON Canada Univ Bremen Bremen Germany

A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices of the graph. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k , whether it is possible to transform one into the other by a sequence of token slides (along edges of the graph) or token jumps (between arbitrary vertices of the graph) such that each intermediate set remains a feasible solution of size k . Many algorithmic questions present themselves in the form of reconfiguration problems: Given the description of an initial system state and the description of a target state, is it possible to transform the system from its initial state into the target one while preserving certain properties of the system in the process? Such questions have received a substantial amount of attention under the so-called combinatorial reconfiguration framework. We consider reconfiguration variants of three fundamental underlying graph vertex-subset problems, namely INDEPENDENT SET, , DOMINATING SET, , and CONNECTED DOMINATING SET. . We survey both older and more recent work on the parameterized complexity of all three problems when parameterized by the number of tokens k . The emphasis will be on positive results and the most common techniques for the design of fixed-parameter tractable algorithms.

关键词： Combinatorial reconfiguration parameterized complexity Independent set Dominating set Connected dominating set Sparse graphs

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the Maximum Exposure Problem

引用

INFORMATION PROCESSING LETTERS 2023年 180卷

作者： Raman, Remi John, J. S. Shahin Subashini, R. Methirumangalath, Subhasree Natl Inst Technol Calicut India

We investigate the parameterized complexity of the Maximum Exposure Problem (MEP). Given a range space (R, P) where R is the set of ranges containing a set P of points and an integer k, MEP asks for k ranges, which on removal results in the maximum number of exposed points. A point p is said to be exposed when p is not contained in any of the ranges in R. The problem is known to be NP-hard. In this paper, we give fixed-parameter tractable results of MEP with respect to different parameterizations.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Maximum Exposure Problem Computational Geometry parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the acyclic matching problem

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期958卷

作者： Hajebi, Sahab Javadi, Ramin Isfahan Univ Technol Dept Math Sci POB 84156-83111 Esfahan Iran Inst Res Fundamental Sci IPM Sch Math POB 19395-5746 Tehran Iran

A matching is a set of edges in a graph with no common endpoint. A matching M is called acyclic if the induced subgraph on the endpoints of the edges in M is acyclic. Given a graph G and an integer k, Acyclic Matching problem seeks for an acyclic matching of size k in G. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs of maximum degree three and arbitrarily large girth. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter k. On the other hand, the problem is fixed parameter tractable with respect to the parameters treewidth, modular-width and (k, c4), where c4 is the number of cycles with length 4 of the input graph. We also prove that the problem is fixed parameter tractable with respect to the parameter k for the line graphs and every proper minor-closed class of graphs (including planar graphs). (c) 2023 Elsevier B.V. All rights reserved.

关键词： Acyclic matching Induced matching Computational complexity parameterized complexity Treewidth Modular-width

来源：评论

学校读者我要写书评

暂无评论

Integer programming in parameterized complexity: Five miniatures

引用

DISCRETE OPTIMIZATION 2022年第Part1期44卷

作者： Gavenciak, Tomas Koutecky, Martin Knop, Dusan Charles Univ Prague Comp Sci Inst Fac Math & Phys Malostranske Namesti 25 Prague Czech Republic Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Thakurova 9 Prague Czech Republic

Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f (k)poly(n). We focus on: Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter;we show which algorithms and tricks are often useful for speed-ups. Minding the poly(n): reducing f (k) often has the unintended consequence of increasing poly(n);so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, Max-q-Cut, and certain other coloring problems by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, indefinite quadratic programs in fixed dimension, parametric integer programs in fixed dimension, and 2-stage stochastic integer programs. (C) 2020

关键词： Graph coloring Sum-coloring parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Special Issue "New Frontiers in parameterized complexity and Algorithms": Foreward by the Guest Editors

引用

ALGORITHMS 2020年第9期13卷

作者： Misra, Neeldhara Rosamond, Frances Zehavi, Meirav Indian Inst Technol Gandhinagar Dept Comp Sci & Engn Palaj 382355 Gandhinagar India Univ Bergen Dept Informat Postboks 7803 N-5020 Bergen Norway Ben Gurion Univ Negev Dept Comp Sci IL-8410501 Beer Sheva Israel

This Special Issue contains eleven articles-surveys and research papers-that represent fresh and ambitious new directions in the area of parameterized complexity. They provide ground-breaking research at the frontiers of knowledge, and they contribute to bridging the gap between theory and practice. The scope and impact of the field continues to increase. Promising avenues and new research challenges are highlighted in this Special Issue.

关键词： FPT parameterized complexity kernelization lower bounds fine-grained Heuristics turbo-charged ETH SETH

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：