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

parameterized Algorithms for Non-separating Trees and Branchings in Digraphs

ALGORITHMICA 2016年第1期76卷 279-296页

作者： Bang-Jensen, Jorgen Saurabh, Saket Simonsen, Sven Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Inst Math Sci Madras Tamil Nadu India

A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer , we can test whether D contains arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP-complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP-complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc-Disjoint Branchings and Non-Disconnecting Out-Branching. In Arc-Disjoint Branchings (Non-Disconnecting Out-Branching), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems. Non-Disconnecting Out-Branching is fixed parameter tractable (FPT) and admits a linear vertex kernel. Arc-Disjoint Branchings is FPT on strong digraphs.

关键词： Branching Spanning tree Fixed parameter tractable parameterized complexity Linear vertex kernel Exponential time algorithm Partitioning problem

来源：评论

学校读者我要写书评

暂无评论

Shortest color-spanning intervals

引用

THEORETICAL COMPUTER SCIENCE 2016年第Part3期609卷 561-568页

作者： Jiang, Minghui Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 = 1. We also obtain some interesting results for the general problem SCSI-t. From the negati... 详细信息

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 <= i <= k, the problem SHORTEST COLOR-SPANNING t INTERVALS (SCSI-t) aims at finding t intervals to cover at least si points of each color i, such that the maximum length of the intervals is minimized. Chen and Misiolek introduced the problem SCSI-1, and presented an algorithm running in O(n) time if the input points are sorted. Khanteimouri et al. gave an O (n(2) logn) time algorithm for the special case of SCSI-2 with s(i) = 1 for all colors i. In this paper, we present an improved algorithm with running time of 0(n2) for SCSI-2 with arbitrary si >= 1. We also obtain some interesting results for the general problem SCSI-t. From the negative direction, we show that approximating SCSI-t within any ratio is NP-hard when t is part of the input, is W[2]-hard when t is the parameter, and is W[1]-hard with both t and k as parameters. Moreover, the NP-hardness and the W[2]-hardness with parameter t hold even if si = 1 for all i. From the positive direction, we show that SCSI-t with si = 1 for all i is fixed-parameter tractable with k as the parameter, and admits an exact algorithm running in 0 (2(k)n . max{k, logn}) time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Color-spanning objects Computational geometry Exact algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth

引用

ALGORITHMICA 2016年第2期75卷 277-294页

作者： Razgon, Igor Univ London Birkbeck Dept Comp Sci & Informat Syst London England

In this paper we prove a space lower bound of for non-deterministic (syntactic) read-once branching programs (nrobps) on functions expressible as cnfs with treewidth at most k of their primal graphs. This lower bound rules out the possibility of fixed-parameter space complexity of nrobps parameterized by k. We use lower bound for nrobps to obtain a quasi-polynomial separation between Free Binary Decision Diagrams and Decision Decomposable Negation Normal Forms, essentially matching the existing upper bound introduced by Beame et al. (Proceedings of the twenty-ninth conference on uncertainty in artificial intelligence, Bellevue, 2013) and thus proving the tightness of the latter.

关键词： Read-once branching programs CNFs Bounded treewidth parameterized complexity Space complexity Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Edge-disjoint packing of stars and cycles

引用

THEORETICAL COMPUTER SCIENCE 2016年 640卷 61-69页

作者： Jiang, Minghui Xia, Ge Zhang, Yong Utah State Univ Dept Comp Sci Logan UT 84322 USA Lafayette Coll Dept Comp Sci Easton PA 18042 USA Kutztown State Univ Dept Comp Sci & Informat Technol Kutztown PA 19530 USA

We study the parameterized complexity of two graph packing problems, EDGE-DISJOINT k-PACKING OF S-STARS and EDGE-DISJOINT k-PACKING OF S-CYCLES. With respect to the choice of parameters, we show that although the two problems are FPT with both k and s as parameters, they are unlikely to be fixed-parameter tractable when parameterized by only k or only s. In terms of kernelization complexity, we show that EDGE-DISJOINT k-PACKING OF S-STARS has a kernel with size polynomial in both k and s, but in contrast, unless NP subset of coNP/poly, EDGE-DISJOINT k-PACKING OF s-CYCLES does not have a kernel with size polynomial in both k and s, and moreover does not have a kernel with size polynomial in s for any fixed k. We also show that EDGE-DISJOINT k-PACKING OF 4-CYCLES admits a 96k(2) kernel in general graphs and a 96k kernel in planar graphs. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Graph packing parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for long directed cycle

引用

INFORMATION PROCESSING LETTERS 2016年第6期116卷 419-422页

作者： Zehavi, Meirav Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

Given a directed graph G and a parameter k, the LONG DIRECTED CYCLE (LDC) problem asks whether G contains a simple cycle on at least k vertices, while the k-PATH problem asks whether G contains a simple path on exactly k vertices. Given a deterministic (randomized) algorithm for k-PATH as a black box, which runs in time t(G, k), we prove that LDC can be solved in deterministic time O*(max{t(G, 2k), 4(k+0(k))}) or in randomized time O*(max{t(G, 2k), 4(k)}). In particular, we get that LDC can be solved in randomized time O*(4(k)). (C) 2016 Elsevier B.V. All rights reserved.

关键词： Algorithms parameterized complexity Long directed cycle k-Path

来源：评论

学校读者我要写书评

暂无评论

Kernelization complexity of possible winner and coalitional manipulation problems in voting

引用

THEORETICAL COMPUTER SCIENCE 2016年 616卷 111-125页

作者： Dey, Palash Misra, Neeldhara Narahari, Y. Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Indian Inst Technol Dept Comp Sci & Engn Gandhinagar India

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge [10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Computational social choice Possible winner Voting Kemelization parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A characterization of b-chromatic and partial Grundy numbers by induced subgraphs

引用

DISCRETE MATHEMATICS 2016年第8期339卷 2157-2167页

作者： Effantin, Brice Gastineau, Nicolas Togni, Olivier Univ Bourgogne Franche Comte CNRS Arts & Metiers LE2I UMR6306 F-21000 Dijon France Univ Lyon 1 CNRS LIRIS UMR5205 F-69622 Villeurbanne France

Gyarfas et al. and Zaker have proven that the Grundy number of a graph G satisfies Gamma(G) >= t if and only if G contains an induced subgraph called a t-atom. The family of t-atoms has bounded order and contains a finite number of graphs. In this article, we introduce equivalents of t-atoms for b-coloring and partial Grundy coloring. This concept is used to prove that determining if phi(G) >= t and partial derivative Gamma(G) >= t (under conditions for the b-coloring), for a graph G, is in XP with parameter t. We illustrate the utility of the concept of t-atoms by giving results on b-critical vertices and edges, on b-perfect graphs and on graphs of girth at least 7. (C) 2016 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Grundy number b-coloring Partial Grundy number

来源：评论

学校读者我要写书评

暂无评论

Anyone But Them: The complexity Challenge for A Resolute Election Controller 17

Anyone But Them: The Complexity Challenge for A Resolute Ele...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Yongjie Yang Jianxin Wang School of Information Science and Engineering Central South University

ISBN: (纸本)9781510855076

We study the voting problems where given is an election associated with a subset J of candidates, and the question is whether we can modify the election in a way so that none of the candidates in J wins the election. The modification operations include either adding some votes/candidates or deleting some votes/candidates. These problems are natural generalizations of destructive control problems where J is a singleton and capture many practical situations. We achieve a broad range of complexity results for a number of single-winner voting systems involving voting rules which are compositions of commonly used voting correspondences, such as Borda, Maximin and Copeland~α, and three tie-breaking schemes, namely the fixed-order, random candidates and random votes. In particular, we achieve polynomial-time solvability results, NP-hardness results, fixed-parameter tractability results as well as XP results. In addition, we study other tie-breaking schemes and show that the complexity of the problems may depend on tie-breaking schemes.

关键词： Destructive control Voting systems Borda Maximin Copeland parameterized complexity vote system Vote iodine complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized Proof complexity

引用

COMPUTATIONAL complexity 2011年第1期20卷 51-85页

作者： Dantchev, Stefan Martin, Barnaby Szeider, Stefan Univ Durham Dept Comp Sci Durham DH1 3LE England

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter (we call such a formula a parameterized contradiction). One could separate the parameterized complexity classes FPT and W[SAT] by showing that there is no fpt-bounded parameterized proof system for parameterized contradictions, i.e., that there is no proof system that admits proofs of size f(k)n (O(1)) where f is a computable function and n represents the size of the propositional formula. By way of a first step, we introduce the system of parameterized tree-like resolution and show that this system is not fpt-bounded. Indeed, we give a general result on the size of shortest tree-like resolution proofs of parameterized contradictions that uniformly encode first-order principles over a universe of size n. We establish a dichotomy theorem that splits the exponential case of Riis's complexity gap theorem into two subcases, one that admits proofs of size f(k)n (O(1)) and one that does not. We also discuss how the set of parameterized contradictions may be embedded into the set of (ordinary) contradictions by the addition of new axioms. When embedded into general (DAG-like) resolution, we demonstrate that the pigeonhole principle has a proof of size 2 (k) n (2). This contrasts with the case of tree-like resolution where the embedded pigeonhole principle falls into the "non-FPT" category of our dichotomy.

关键词： Propositional proof complexity parameterized complexity complexity gap theorems

来源：评论

学校读者我要写书评

暂无评论

parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers 17

Parameterized Dichotomy of Choosing Committees Based on Appr...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Palash Dey Neeldhara Misra Y. Narahari Tata Institute of Fundamental Research Indian Institute of Technology Indian Institute of Science

ISBN: (纸本)9781510855076

Approval ballots provide an opportunity for agents to make a comment about every candidate, without incurring the overhead of determining a full ranking on the set of candidates; they are very natural for many practical settings. We study the computational complexity of the committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outliers render the committee selection problem intractable for approval, net approval, and minisum approval voting rules. We next study the parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter namely the number of candidates outside the committee); and the number of outliers (and its dual parameter namely the number of non-outliers). For approval, net approval, and minisum approval voting rules, we provide a dichotomous result, which resolves the parameterized complexity of this problem for all subsets of the above five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters).

关键词： Voting Committee selection Outliers Social choice parameterized complexity outliers Vote approval Committees parameterization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：