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

FO MODEL CHECKING OF INTERVAL GRAPHS

LOGICAL METHODS IN COMPUTER SCIENCE 2015年第4期11卷

作者： Ganian, Robert Hlineny, Petr Kral', Daniel Obdrzalek, Jan Schwartz, Jarett Teska, Jakub TU Wien Algorithms & Complex Grp Favoritenstr 9-11 A-1040 Vienna Austria Masaryk Univ Fac Informat Brno 62100 Czech Republic Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Univ W Bohemia Fac Sci Appl Plzen 30614 Czech Republic

We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that FO model checking and successor-invariant FO model checking can be solved in time O(n log n) for n-vertex interval graphs with representations containing only intervals with lengths from a prescribed finite set. We complement this result by showing that the same is not true if the lengths are restricted to any set that is dense in an open subset, e.g. in the set (1;1 + epsilon).

关键词： first-order model checking parameterized complexity interval graph clique-width

来源：评论

学校读者我要写书评

暂无评论

Some Hard Families of parameterized Counting Problems

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2015年第3期7卷 11-11页

作者： Jerrum, Mark Meeks, Kitty Queen Mary Univ London Sch Math Sci Mile End Rd London E1 4NS England Queen Mary Univ London London E1 4NS England

We consider parameterized subgraph counting problems of the following form: given a graph G, how many k-tuples of its vertices induce a subgraph with a given property? A number of such problems are known to be #W[1]-complete;here, we substantially generalize some of these existing results by proving hardness for two large families of such problems. We demonstrate that it is #W[1]-hard to count the number of k-vertex subgraphs having any property where the number of distinct edge densities of labeled subgraphs that satisfy the property is o(k(2)). In the special case in which the property in question depends only on the number of edges in the subgraph, we give a strengthening of this result, which leads to our second family of hard problems.

关键词： Counting complexity parameterized complexity Ramsey theory

来源：评论

学校读者我要写书评

暂无评论

Large-Scale Election Campaigns: Combinatorial Shift Bribery 15

Large-Scale Election Campaigns: Combinatorial Shift Bribery

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Robert Bredereck Piotr Faliszewski Rolf Niedermeier Nimrod Talmon TU Berlin AGH University

ISBN: (纸本)9781450337694

We study the complexity of a combinatorial variant of the Shift Bribery problem in elections. In the standard Shift Bribery problem, we are given an election where each voter has a preference order over the candidate set and where an outside agent, the briber, can pay each voter to rank the briber's favorite candidate a given number of positions higher. The goal is to ensure the victory of the briber's preferred candidate. The combinatorial variant of the problem, introduced in this paper, models settings where it is possible to affect the position of the preferred candidate in multiple votes, either positively or negatively, with a single bribery action. This variant of the problem is particularly interesting in the context of large-scale campaign management problems (which, from the technical side, are modeled as bribery problems). We show that, in general, the combinatorial variant of the problem is highly intractable (NP-hard, hard in the parameterized sense, and hard to approximate), but we provide some (approximation) algorithms for natural restricted cases.

关键词： Campaign management Preference aggregation Voting Computational complexity parameterized complexity Fixed-parameter tractability Approximation algorithms Approximation algorithms Vote complexity classes candidate species Shift

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of the maximum independent set problem and the speed of hereditary properties

引用

Electronic Notes in Discrete Mathematics 2009年 34卷 127-131页

作者： Lozin, Vadim V. DIMAP Mathematics Institute University of Warwick Coventry United Kingdom

For a hereditary class X, the number Xn of n-vertex graphs in X (also known as the speed of X) satisfies limn → ∞ frac(log2 Xn, ((n;2))) = 1 - frac(1, k (X)) where k (X) is a natural number called the index of the c... 详细信息

For a hereditary class X, the number X_n of n-vertex graphs in X (also known as the speed of X) satisfies lim_{n → ∞} frac(log₂ X_n, ((n;2))) = 1 - frac(1, k (X)) where k (X) is a natural number called the index of the class. Each class X of index k > 1 can be approximated by a minimal class of the same index. In this paper, we use Ramsey theory to show that the maximum independent set problem is fixed-parameter tractable in all minimal classes of index k for all values of k. © 2009 Elsevier B.V. All rights reserved.

关键词： Hereditary properties parameterized complexity Ramsey Theory

来源：评论

学校读者我要写书评

暂无评论

Kernelization complexity of Possible Winner and Coalitional Manipulation Problems in Voting 15

Kernelization Complexity of Possible Winner and Coalitional ...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Palash Dey Neeldhara Misra Y. Narahari Department of Computer Science and Automation Indian Institute of Science

ISBN: (纸本)9781450337694

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. 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 include the Borda voting rule do 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.

关键词： Computational social choice Possible winner Voting Kernelization parameterized complexity Vote Polynomial Scoring Seeds

来源：评论

学校读者我要写书评

暂无评论

On Cutwidth parameterized by Vertex Cover

引用

ALGORITHMICA 2014年第4期68卷 940-953页

作者： Cygan, Marek Lokshtanov, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saurabh, Saket Univ Warsaw Inst Informat PL-02097 Warsaw Poland Univ Calif San Diego La Jolla CA 92093 USA Univ Bergen Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 (k) n (O(1))). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 (n/2) n (O(1))) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NPaS dagger coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011;SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.

关键词： Cutwidth Vertex cover parameterization parameterized complexity Composition algorithms Polynomial kernel

来源：评论

学校读者我要写书评

暂无评论

How Hard is Control in Multi-Peaked Elections: A parameterized Study 15

How Hard is Control in Multi-Peaked Elections: A Parameteriz...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Yongjie Yang Jiong Guo Universitat des Saarlandes School of Computer Science and Technology

ISBN: (纸本)9781450337717

We study the complexity of voting control problems in multi-peaked elections. In particular, we focus on the constructive/destructive control by adding/deleting votes under Condorcet, Maximin and Copeland~α voting systems. We show that the NP-hardness of these problems (except for the destructive control by adding/deleting votes under Condorcet, which is polynomial-time solvable in the general case) hold even in k-peaked elections with k being a very small constant. Furthermore, from the parameterized complexity point of view, our reductions actually show that these problems are W[1]-hard in k-peaked elections with k = 3, 4, with respect to the number of added/deleted votes.

关键词： Single-peaked generalization Multi-peaked parameterized complexity Election control Condorcet Maximin Copeland

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of multiple-interval graph problems

引用

THEORETICAL COMPUTER SCIENCE 2009年第1期410卷 53-61页

作者： Fellows, Michael R. Hermelin, Danny Rosamond, Frances Vialette, Stephane Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Univ Newcastle Callaghan NSW 2308 Australia Univ Paris Sud Fac Sci Orsay CNRS LRIUMR 8623 F-91405 Orsay France

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we Study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k-INDEPENDENT SET, k-DOMINATING SET, and k-CLIQUE, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k-CLIQUE is in FPT, while k-INDEPENDENT SET and k-DOMINATING SET are both W[1]-hard. We also prove that k-INDEPENDENT DOMINATING SET, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k-MULTICOLORED CLIQUE problem, a variant of k-CLIQUE. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Multiple intervals Independent set Dominating set Clique W-hardness parameterized complexity Multicolored clique

来源：评论

学校读者我要写书评

暂无评论

complexity results for rainbow matchings

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期524卷 27-33页

作者： Le, Van Bang Pfender, Florian Univ Rostock Inst Informat D-18055 Rostock Germany Univ Colorado Dept Math & Stat Denver CO 80202 USA

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. We address the complexity issue of the following problem, MAX RAINBOW MATCHING: Given an edge-colored graph G, how large is the largest rainbow matching in G? We present several sharp contrasts in the complexity of this problem. We show, among others, that MAX RAINBOW MATCHING can be approximated by a polynomial algorithm with approximation ratio 2/3 - epsilon. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored linear forests without a 5-vertex path, and is solvable in polynomial time for edge-colored forests without a 4-vertex path. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored trees without an 8-vertex path, and is solvable in polynomial time for edge-colored trees without a 7-vertex path. MAX RAINBOW MATCHING is APX-complete, even when restricted to properly edge-colored paths. These results provide a dichotomy theorem for the complexity of the problem on forests and trees in terms of forbidding paths. The latter is somewhat surprising, since, to the best of our knowledge, no (unweighted) graph problem prior to our result is known to be NP-hard for simple paths. We also address the parameterized complexity of the problem. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Rainbow matching Computational complexity NP-completeness APX-completeness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for vertex partitioning problems parameterized by clique-width

引用

THEORETICAL COMPUTER SCIENCE 2014年 535卷 16-24页

作者： Oum, Sang-il Saether, Sigve Hortemo Vatshelle, Martin Korea Adv Inst Sci & Technol Dept Math Sci Taejon 305701 South Korea Univ Bergen Dept Informat N-5020 Bergen Norway

Many NP-hard problems, such as DOMINATING SET, are FPT parameterized by clique-width. For graphs of clique-width k given with a k-expression, DOMINATING SET can be solved in 4(k)n(O(1)) time. However, no FPT algorithm is known for computing an optimal k-expression. For a graph of clique-width k, if we rely on known algorithms to compute a (2(3k)-1)-expression via rank-width and then solving DOMINATING SET using the (2(3k)-1)-expression, the above algorithm will only give a runtime of 4(23k)n(O(1)). There have been results which overcome this exponential jump;the best known algorithm can solve DOMINATING SET in time 2(O(k2))n(O(1)) by avoiding constructing a k-expression Bui-Xuan et al. (2013) [7]. We improve this to 2O((k logk))n(O(1)). Indeed, we show that for a graph of clique-width k, a large class of domination and partitioning problems (LC-VSP), including DOMINATING SET, can be solved in 2(O(k log k))n(O(1)). Our main tool is a variant of rank-width using the rank of a 0-1 matrix over the rational field instead of the binary field. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Clique-width parameterized complexity Dynamic programming Generalized domination Rank-width

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：