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

parameterized complexity of candidate nomination for elections based on positional scoring rules

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2024年第2期38卷 28-28页

作者： Schlotter, Ildiko Cechlarova, Katarina Trellova, Diana HUN REN Ctr Econ & Reg Stud Budapest Hungary Budapest Univ Technol & Econ Budapest Hungary Safarik Univ Fac Sci Inst Math Kosice Slovakia

Consider elections where the set of candidates is partitioned into parties, and each party must nominate exactly one candidate. The Possible President problem asks whether some candidate of a given party can become the unique winner of the election for some nominations from other parties. We perform a multivariate computational complexity analysis of Possible President for several classes of elections based on positional scoring rules. We consider the following parameters: the size of the largest party, the number of parties, the number of voters and the number of voter types. We provide a complete computational map of Possible President in the sense that for each choice of the four possible parameters as (i) constant, (ii) parameter, or (iii) unbounded, we classify the computational complexity of the resulting problem as either polynomial-time solvable or NP-complete, and for parameterized versions as either fixed-parameter tractable or W[1]-hard with respect to the parameters considered.

关键词： Computational social choice Candidate nomination Positional scoring rules parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of completeness reasoning for conjunctive queries

引用

THEORETICAL COMPUTER SCIENCE 2021年 864卷 34-49页

作者： Liu, Xianmin Li, Jianzhong Li, Yingshu Feng, Yuqiang Harbin Inst Technol Harbin 150001 Heilongjiang Peoples R China Georgia State Univ Atlanta GA 30303 USA

Incompleteness management has become a popular research topic and been viewed in many applications in the area of data quality and data management. Traditional methods for handling incompleteness assume data is totally complete or incomplete. However, in practical applications, data is often partial complete, which means that data is not totally complete but some special parts of the data satisfying given semantic specifications are complete. Intuitively, partial complete data can still give complete answers for queries consistent with the semantic specifications. Therefore, it is highly needed to study the fundamental problems for managing partial complete data. However, as far as known by us, there are only few works focusing on this area. The most important and fundamental problem, completeness reasoning, is studied from the aspect of parameterized complexity by this paper. The completeness reasoning problem, TC-QC (Table Completeness to Query Completeness), is first formally defined and studied by Razniewski et al. [1]. Given completeness statements of data, the goal of the TC-QC problem is to determine whether the result of a special query Q is complete, that is to reason query completeness based on given data completeness. Razniewski et al. have shown that the TC-QC problem is NP-hard even for conjunctive queries, and a natural and interesting question is whether or not TC-QC can be solved efficiently by parameterized algorithms. To answer that, the parameterized complexities of completeness reasoning for conjunctive queries are studied by the paper. First, it is shown that, considering the parameterizations defined by the size of query completeness or table completeness, the parameterized TC-QC problem for conjunctive queries is para-NP-complete, which strongly indicate that the TC-QC problems parameterized by the above two parameters do not admit fixed-parameter tractable algorithms. Then, for more special cases parameterized by different constraints on quer

关键词： Completeness reasoning parameterized complexity Conjunctive queries

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of perfectly matched sets *,**

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期958卷

作者： Agrawal, Akanksha Bhattacharjee, Sutanay Jana, Satyabrata Sahu, Abhishek Indian Inst Technol Madras Chennai India Homi Bhabha Natl Inst Natl Inst Sci Educ & Res OCC Bhubaneswar India HBNI Inst Math Sci Chennai India

For an undirected graph G, a pair of vertex disjoint subsets (A, B) is a pair of perfectly matched sets if each vertex in A (resp. B) has exactly one neighbor in B (resp. A). In the above, the size of the pair is |A| (= |B|). Given a graph G and a positive integer k, the PERFECTLY MATCHED SETS problem asks whether there exists a pair of perfectly matched sets of size at least k in G. This problem is known to be NP-hard on planar graphs and W[1]-hard on general graphs, when parameterized by k. However, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we study the problem parameterized by k, and design FPT algorithms for: i) apex-minor-free graphs running in time 2O( k) center dot nO(1), and ii) Kb,b-free graphs. We obtain a linear kernel for planar graphs and kO(d)-sized kernel for d-degenerate graphs. It is known that the problem is W[1]-hard on chordal graphs, in fact on split graphs, parameterized by k. We complement this hardness result by designing a polynomial-time algorithm for interval graphs.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Perfectly matched sets parameterized complexity Apex -minor -free graphs d -degenerate graphs Planar graphs Interval graphs

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of fair feedback vertex set problem

引用

THEORETICAL COMPUTER SCIENCE 2021年 867卷 1-12页

作者： Kanesh, Lawqueen Maity, Soumen Muluk, Komal Saurabh, Saket Indian Inst Sci Educ & Res Pune Maharashtra India Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway

Given a graph G =(V, E), a subset S subset of V(G) is said to be a feedback vertex set of Gif G - Sis a forest. In theFeedback Vertex Set (FVS) problem, we are given an undirected graph G, and a positive integer k, the question is whether there exists a feedback vertex set of size at most k. In this paper, we study three variants of the FVS problem: Unrestricted Fair FVS, Restricted Fair FVS, andRelaxed Fair FVS. InUnrestricted Fair FVS, we are given a graph Gand a positive integer l, the question is does there exist a feedback vertex set S subset of V(G) (of any size) such that for every vertex v is an element of V(G), vhas at most l neighbours in S. First, we studyUnrestricted Fair FVSfrom different parameterizations such as treewidth, treedepth, and neighbourhood diversity and obtain several results (both tractability and intractability). Next, we studyRestricted Fair FVS, where we are also given an integer kin the input and we demand the size of Sto be at most k. This problem is trivially NP-complete;we show thatRestricted Fair FVSwhen parameterized by the solution size kand the maximum degree Delta of the graph G, admits a kernel of size O(Delta k). Finally, we study theRelaxed Fair FVSproblem, where we want that the size of Sis at most kand for every vertex voutside S, vhas at most l neighbours in S. We give an FPT algorithm forRelaxed Fair FVSproblem running in time c(k)n(O(1)), for a fixed constant c. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Feedback vertex set parameterized complexity FPT W[1]-hard

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of abduction in Schaefer's framework

引用

JOURNAL OF LOGIC AND COMPUTATION 2021年第1期31卷 266-296页

作者： Mahmood, Yasir Meier, Arne Schmidt, Johannes Leibniz Univ Hannover Inst Theoret Informat Appelstr 4 D-30167 Hannover Germany Jonkoping Univ Sch Engn Dept Comp Sci & Informat Gjuterigatan 5 S-55111 Jonkoping Sweden

Abductive reasoning is a non-monotonic formalism stemming from the work of Peirce. It describes the process of deriving the most plausible explanations of known facts. Considering the positive version, asking for sets of variables as explanations, we study, besides the problem of wether there exists a set of explanations, two explanation size limited variants of this reasoning problem (less than or equal to, and equal to a given size bound). In this paper, we present a thorough two-dimensional classification of these problems: the first dimension is regarding the parameterized complexity under a wealth of different parameterizations, and the second dimension spans through all possible Boolean fragments of these problems in Schaefer's constraint satisfaction framework with co-clones (T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, R.J. Lipton, W.A. Burkhard, W.J. Savitch, E.P. Friedman, A.V. Aho eds, pp. 216-226. ACM, 1978). Thereby, we almost complete the parameterized complexity classification program initiated by Fellows et al. (The parameterized complexity of abduction. In Proceedings of the Twenty-Sixth AAAI Conference on Articial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, J. Homann, B. Selman eds. AAAI Press, 2012), partially building on the results by Nordh and Zanuttini (What makes propositional abduction tractable. Artificial Intelligence, 172, 1245-1284, 2008). In this process, we outline a fine-grained analysis of the inherent parameterized intractability of these problems and pinpoint their FPT parts. As the standard algebraic approach is not applicable to our problems, we develop an alternative method that makes the algebraic tools partially available again.

关键词： parameterized complexity abduction non-monotonic reasoning Schaefer's framework co-clones

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the Perfect Phylogeny Problem 49th

On the Parameterized Complexity of the Perfect Phylogeny Pro...

引用

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

作者： de Vlas, Jorke M. Univ Utrecht Utrecht Netherlands Linkoping Univ Linkoping Sweden

ISBN: (纸本)9783031521126;9783031521133

This paper categorizes the parameterized complexity of the algorithmic problems PERFECT PHYLOGENY and TRIANGULATING COLORED GRAPHS when parameterized by the number of genes and colors, respectively. We show that they are complete for the parameterized complexity class XALP using a reduction from TREE-CHAINED MULTICOLOR INDEPENDENT SET and a proof of membership. We introduce the problem TRIANGULATING MULTICOLORED GRAPHS as a stepping stone and prove XALP-completeness for this problem as well. We also show that, assuming the Exponential Time Hypothesis, there exists no algorithm that solves any of these problems in time f(k)n(o(k)), where n is the input size, k the parameter, and f any computable function.

关键词： Perfect phylogeny Triangulated graphs XALP parameterized complexity W-hierarchy

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of Terminal Monitoring Set 1

引用

18th International Conference and Workshops on Algorithms and Computation (WALCOM)

作者： Aravind, N. R. Saxena, Roopam IIT Hyderabad Dept Comp Sci & Engn Hyderabad Telangana India

ISBN: (数字)9789819705665

ISBN: (纸本)9789819705658;9789819705665

In Terminal Monitoring Set (TMS), the input is an undirected graph G = (V, E), together with a collection T of terminal pairs and the goal is to find a subset S of minimum size that hits a shortest path between every pair of terminals. We show that this problem is W[2]-hard with respect to solution size. On the positive side, we show that TMS is fixed parameter tractable with respect to solution size plus distance to cluster, solution size plus neighborhood diversity, and feedback edge number. For the weighted version of the problem, we obtain a FPT algorithm with respect to vertex cover number, and for a relaxed version of the problem, we show that it is W[1]-hard with respect to solution size plus feedback vertex number.

关键词： monitoring set hitting set hub location parameterized complexity fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Reconfiguration of Connected Dominating Sets

引用

ALGORITHMICA 2022年第2期84卷 482-509页

作者： Lokshtanov, Daniel Mouawad, Amer E. Panolan, Fahad Siebertz, Sebastian Univ Calif Santa Barbara Santa Barbara CA 93106 USA Amer Univ Beirut Dept Comp Sci Beirut Lebanon IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Univ Bremen Bremen Germany

In a reconfiguration version of a decision problem Q the input is an instance of Q and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the CONNECTED DOMINATING SET RECONFIGURATION problem (CDS- R). It was shown in previous work that the DOMINATING SET RECONFIGURATION problem (DS- R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K-d(,d) as a subgraph, for some constant d >= 1. We show that the additional connectivity constraint makes the problem much harder, namely, that CDS- R is W[1]-hard parameterized by k + l, the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS- R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs.

关键词： Reconfiguration parameterized complexity Connected dominating set Graph structure theory

来源：评论

学校读者我要写书评

暂无评论

Synchronizing words and monoid factorization, yielding a new parameterized complexity class?

引用

MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE 2022年第2期32卷 189-215页

作者： Fernau, Henning Bruchertseifer, Jens Univ Trier Theoret Informat Abt Informatikwissensch Fachbereich 4 Trier Germany

The concept of a synchronizing word is a very important notion in the theory of finite automata. We consider the associated decision problem to decide if a given DFA possesses a synchronizing word of length at most k, where k is the standard parameter. We show that this problem DFA-SW is equivalent to the problem MONOID FACTORIZATION introduced by Cai, Chen, Downey, and Fellows. Apart from the known W[2]-hardness results, we show that these problems belong to A[2], W[P], and WNL. This indicates that DFA-SW is not complete for any of these classes, and hence, we suggest a new parameterized complexity class W[Sync] as a proper home for these (and more) problems. We present quite a number of problems that belong to W[Sync] or are hard or complete for this new class.

关键词： Synchronizing word deterministic finite automaton (DFA) parameterized complexity Monoid Factorization W[Sync]

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of envy-free resource allocation in social networks

引用

ARTIFICIAL INTELLIGENCE 2023年 315卷

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Ordyniak, Sebastian Royal Holloway Univ London Dept Comp Sci London England TU Wien Algorithms & Complex Grp Vienna Austria Univ Leeds Sch Comp Leeds England

We consider the classical problem of allocating indivisible resources among agents in an envy-free (and, where applicable, proportional) way. Recently, the basic model was enriched by introducing the concept of a social network which allows to capture situations where agents might not have full information about the allocation of all resources. We initiate the study of the parameterized complexity of these resource allocation problems by considering natural parameters which capture structural properties of the network and similarities between agents and resources. In particular, we show that even very general fragments of the considered problems become tractable as long as the social network has constant treewidth or clique-width. We complement our results with matching lower bounds which show that our algorithms cannot be substantially improved. (c) 2022 Published by Elsevier B.V.

关键词： Resource allocation parameterized complexity Computational social choice Treewidth Clique-width

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：