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

International Conference on Autonomous Agents and Multiagent Systems

作者： Hooyeon Lee Virginia Vassilevska Williams Moloco Inc. Massachusetts Institute of Technology

ISBN: (纸本)9781510855076

We consider the Group Activity Selection Problem (GASP) in which a group of agents need to be assigned to activities, subject to agent preferences and stability conditions. In GASP, the agents announce dichotomic preferences on which (activity, number-of-participant) pairs are acceptable to them. We consider five solution concepts of assignments: (1) individual rationality (everyone who is assigned to an activity is willing to participate), (2) (Nash) stability (no agent wants to deviate from the assignment), (3) envy-freeness (no agent is envious of someone else's assignment), (4) stability and envy-freeness, and (5) perfection (everyone is assigned and willing to participate). It is known that finding an assignment of a given size with any of these properties is NP-complete. We study the complexity of GASPon a finer scale, through the lens of parameterized complexity. We show that the solution concepts above differ substantially, when parameterized by the size of the solution (the number of assigned agents or the number of used activities). In particular, finding an individually rational assignment is fixed parameter tractable, yet other solutions concepts are less tractable (W[1]- and W[2]-hard) even under very natural restrictions on inputs.

关键词： parameterized complexity Fixed parameter tractability W-hierarchy Individual rationality Stability Envy-free Agents activity solution concept GASP parameterization

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity dichotomy for STEINER MULTICUT

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第6期82卷 1020-1043页

作者： Bringmann, Karl Hermelin, Danny Mnich, Matthias van Leeuwen, Erik Jan Swiss Fed Inst Technol Inst Theoret Comp Sci Zurich Switzerland Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Bonn Bonn Germany Max Planck Inst Informat Heidelberg Germany

We consider the STEINER MULTICUT problem, which asks, given an undirected graph G, a collection tau = {T-1,, T-t}, T-i subset of V (G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T-i at least one pair of terminals is in different connected components of G - S. We provide a dichotomy of the parameterized complexity of STEINER MULTICUT. For any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable, W[1} -hard, or (para-)NP-complete. Our characterization includes a dichotomy for STEINER MULTICUT on trees as well as a polynomial time versus NP-hardness dichotomy (by restricting k, t, p, tw(G) to constant or unbounded). (C) 2016 Elsevier Inc. All rights reserved.

关键词： Cut problems Steiner multicut parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of the MINCCA Problem on Graphs of Bounded Decomposability 1

引用

42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Gozupek, Didem Ozkan, Sibel Paul, Christophe Sau, Ignasi Shalom, Mordechai Gebze Tech Univ Dept Comp Engn Kocaeli Turkey Gebze Tech Univ Dept Math Kocaeli Turkey Univ Montpellier LIRMM CNRS Montpellier France TelHai Coll IL-12210 Upper Galilee Israel Bogazici Univ Dept Ind Engn Istanbul Turkey

ISBN: (数字)9783662535363

ISBN: (纸本)9783662535363;9783662535356

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The Minimum Changeover Cost Arborescence (MINCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gozupek et al. [14] that the MINCCA problem is FPT when parameterized by the treewidth and the maximum degree of the input graph. In this article we present the following results for MINCCA: the problem is W[1]-hard parameterized by the treedepth of the input graph, even on graphs of average degree at most 8. In particular, it is W[1]-hard parameterized by the treewidth of the input graph, which answers the main open problem of [14];it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph;it is FPT parameterized by the star tree-cutwidth of the input graph, which is a slightly restricted version of tree-cutwidth. This result strictly generalizes the FPT result given in [14];it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs.

关键词： Minimum Changeover Cost Arborescence parameterized complexity FPT algorithm Treewidth Dynamic programming Planar graph

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the hardness of labeled correlation clustering problem: A parameterized complexity view

引用

THEORETICAL COMPUTER SCIENCE 2016年第Part3期609卷 583-593页

作者： Liu, Xianmin Li, Jianzhong Gao, Hong Harbin Inst Technol Harbin 150001 Peoples R China

Motivated by practical applications, the Labeled Correlation Clustering problem, a variant of Correlation Clustering problem, is formally defined and studied in this paper. Since the problem is NP-complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied. For the two parameterized problems which are fixed-parameter-tractable, the lower bounds of them are analyzed under SETH (Strong Exponential Time Hypothesis). (C) 2015 Elsevier B.V. All rights reserved.

关键词： Labeled correlation clustering parameterized complexity Lower bound Strong Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

On parameterized complexity of Group Activity Selection Problems on Social Networks 17

On Parameterized Complexity of Group Activity Selection Prob...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Ayumi Igarashi Robert Bredereck Edith Elkind University of Oxford

ISBN: (纸本)9781510855076

In Group Activity Selection Problem with graph structure (gGASP), players form coalitions to participate in activities and have preferences over pairs of the form (activity, group size); moreover, a group of players can only engage in the same activity if the members of the group form a connected subset of the underlying communication structure. We study the parameterized complexity of finding outcomes of gGASP that are Nash stable, individually stable or core stable. For the parameter 'number of activities', we propose an FPT algorithm for Nash stability for the case where the social network is acyclic and obtain a W[1]-hardness result for cliques (i.e., for classic GASP); similar results hold for individual stability. In contrast, finding a core stable outcome is hard even if the number of activities is bounded by a small constant, both for classic GASP and when the social network is a star For the parameter 'number of players', all problems we consider are in XP for arbitrary social networks; on the other hand, we prove W[1]-hardness results with respect to the parameter 'number of players' for the case where the social network is a clique (i.e., for classic GASP).

关键词： Group activity selection problems Social networks parameterized complexity Social Networks Social Capital Social Media Players GASP activity parameterization

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Discrete Morse Theory

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2016年第1期42卷 6-6页

作者： Burton, Benjamin A. Lewiner, Thomas Paixao, Joao Spreer, Jonathan Univ Queensland Sch Math & Phys Brisbane Qld 4072 Australia Pontificia Univ Catolica Rio de Janeiro Dept Matemat Rua Marques Sao Vicente 225 BR-22451900 Rio De Janeiro RJ Brazil Univ Fed Rio de Janeiro Dept Ciencia Computacao BR-21941 Rio De Janeiro Brazil

Optimal Morse matchings reveal essential structures of cell complexes that lead to powerful tools to study discrete geometrical objects, in particular, discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds through a reduction to the erasability problem. Here, we refine the study of the complexity of problems related to discrete Morse theory in terms of parameterized complexity. On the one hand, we prove that the erasability problem is W[P]-complete on the natural parameter. On the other hand, we propose an algorithm for computing optimal Morse matchings on triangulations of 3-manifolds, which is fixed-parameter tractable in the treewidth of the bipartite graph representing the adjacency of the 1- and 2-simplices. This algorithm also shows fixed-parameter tractability for problems such as erasability and maximum alternating cycle-free matching. We further show that these results are also true when the treewidth of the dual graph of the triangulated 3-manifold is bounded. Finally, we discuss the topological significance of the chosen parameters and investigate the respective treewidths of simplicial and generalized triangulations of 3-manifolds.

关键词： Algorithms Theory Alternating cycle-free matching collapsibility computational topology discrete Morse theory erasability fixed-parameter tractability parameterized complexity treewidth W[P]-completeness

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Synchronization and Road Coloring

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2015年第1期17卷 283-305页

作者： Vorel, Vojtech Roman, Adam Charles Univ Prague Fac Math & Phys Prague Czech Republic Jagiellonian Univ Inst Comp Sci Krakow Poland

First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.

关键词： synchronizing word reset word Road Coloring Problem synchronizing automata parameterized complexity Cerny conjecture

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity analysis for the Closest String with Wildcards problem

引用

THEORETICAL COMPUTER SCIENCE 2015年 600卷 11-18页

作者： Hermelin, Danny Rozenberg, Liat Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Haifa IL-31999 Haifa Israel

The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized complexity The closest string problem Fixed-parameter algorithms Computational biology

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting

引用

FUNDAMENTA INFORMATICAE 2015年第4期136卷 297-316页

作者： Creignou, Nadia Vollmer, Heribert Aix Marseille Univ CNRS LIF UMR 7279 F-13288 Marseille France Leibniz Univ Hannover Inst Theoret Informat D-30167 Hannover Germany

We consider the weighted satisfiability problem for Boolean circuits and propositional formule, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and initiate a systematic study of the complexity of its fragments. Only the monotone fragment has been considered so far and proven to be of same complexity as the unrestricted problems. Here, we consider all fragments obtained by semantically restricting circuits or formule to contain only gates (connectives) from a fixed set B of Boolean functions. We obtain a dichotomy result by showing that for each such B, the weighted satisfiability problems are either W [P] -complete (for circuits) or W [SAT] -complete (for formule) or efficiently solvable. We also consider the related enumeration and counting problems.

关键词： parameterized complexity weighted satisfiability parameterized counting complexity polynomial-delay enumeration Post's lattice

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：