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

The parameterized complexity of probability amplification

INFORMATION PROCESSING LETTERS 2008年第1期109卷 46-53页

作者： Montoya, J. Andres Univ Ind Santander Escuela Matemat Bucaramanga Colombia

In this paper we Study the parameterized complexity of probability amplification for some parameterized probabilistic classes. We prove that it is very Unlikely that W vertical bar P vertical bar has the probability a... 详细信息

关键词： Computational complexity parameterized complexity Probabilistic classes Probability amplification

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of maximality and minimality problems

引用

ANNALS OF PURE AND APPLIED LOGIC 2008年第1期151卷 22-61页

作者： Chen, Yijia Flum, Joerg Univ Freiburg Abt Math Log D-79104 Freiburg Germany Shanghai Jiao Tong Univ Shanghai Peoples R China

Many parameterized problems (such as the clique problem and the dominating set problem) ask, given an instance and a natural number k as parameter, whether there is a solution of size k. We analyze the relationship between the complexity of such a problem and the corresponding maximality (minimality) problem asking for a solution of size k maximal (minimal) with respect to set inclusion. As our results show, many maximality problems increase the parameterized complexity, while "in terms of the W-hierarchy" minimality problems do not increase the complexity. We also address the corresponding construction, listing, and counting problems. (C) 2007 Elsevier B.V. All rights reserved.

关键词： parameterized complexity maximality problems minimality problems fagin-definability

来源：评论

学校读者我要写书评

暂无评论

Obtížné problémy vzhledem k parametru různorodost sousedství

Obtížné problémy vzhledem k parametru různorodost souse...

引用

作者： Koutecký, Martin Charles University of Prague

parameterized complexity is a part of computer science dealing with the computational complexity of problems measured not only by the length of their input but also some parameter of the input. Nei- ghborhood diversity is a recently introduced parameter describing a certain structure of a graph. is parameter is aractive for resear especially because some problems whi are hard with respect to other parameters that are incomparable with neighborhood diversity become fixed-parameter tractable with respect to neighborhood diversity. In this thesis we show fixed-parameter tractability for three problems that are hard with respect to treewidth. is constitutes the main part of this thesis and it is our original work. Next it contains an overview of other interesting problems and also a survey of the state of the art in the area of parameters for sparse and dense graphs. 1

关键词： parameterized complexity dense graphs neighborhood diversity

来源：评论

学校读者我要写书评

暂无评论

Does Treewidth Help in Modal Satisfiability?

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2013年第3期14卷 18-18页

作者： Praveen, M. Inst Math Sci Madras 600113 Tamil Nadu India

Many tractable algorithms for solving the Constraint Satisfaction Problem (CSP) have been developed using the notion of the treewidth of some graph derived from the input CSP instance. In particular, the incidence graph of the CSP instance is one such graph. We introduce the notion of an incidence graph for modal logic formulas in a certain normal form. We investigate the parameterized complexity of modal satisfiability with the modal depth of the formula and the treewidth of the incidence graph as parameters. For various combinations of Euclidean, reflexive, symmetric, and transitive models, we show either that modal satisfiability is Fixed Parameter Tractable (FPT), or that it is W[1]-hard. In particular, modal satisfiability in general models is FPT, while it is W[1]-hard in transitive models. As might be expected, modal satisfiability in transitive and Euclidean models is FPT.

关键词： Algorithms Theory parameterized complexity satisfiability treewidth

来源：评论

学校读者我要写书评

暂无评论

complexity of Optimal Lobbying in Threshold Aggregation 13

Complexity of Optimal Lobbying in Threshold Aggregation

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Ilan Nehama Hebrew University of Jerusalem

ISBN: (纸本)9781627487665;1627487662

Optimal Lobbying is the problem a lobbyist or a campaign manager faces in a full-information voting scenario of a multi-issue referendum when trying to influence the result. The Lobby is faced with a profile that specifies for each voter and each issue whether the voter approves or rejects the issue, and seeks to find the smallest set of voters it must influence to change their vote, for a desired outcome to be obtained. We study the computational complexity of Optimal Lobbying when the issues are aggregated using an anonymous monotone function and the family of desired outcomes is an upward-closed family. We analyze this problem with regard to two parameters: the minimal number of supporters needed to pass an issue, and the size of the maximal minter of the desired set. We show that for extreme values of the parameters, the problem is tractable, and provide algorithms. On the other hand, we prove intractability of the problem for the complementary cases, which are most of the values of the parameters.

关键词： Optimal lobbying Computational complexity Threshold function parameterized complexity Threshold Function complexity classes Lobbying Vote MONOTONE FUNCTIONS extremum values

来源：评论

学校读者我要写书评

暂无评论

On connected two communities 13

On connected two communities

引用

Proceedings of the Thirty-Sixth Australasian Computer Science Conference - Volume 135

作者： V. Estivill-Castro Mahdi Parsa Griffith University Nathan Australia

ISBN: (纸本)9781921770203

We say that there is a community structure in a graph when the nodes of the graph can be partitioned into groups (communities) such that each group is internally more densely connected than with the rest of the graph. However, the challenge is to specify what is to be dense, and what is relatively more connected (there seems to exist an analogous situation to what is a cluster in unsupervized learning). Recently, Olsen (2012) provided a general definition that seemed to be significantly more generic that others. We make two observations regarding such definition. (1) First, we show that finding a community structure with two equal size communities is NP-complete (Uniform 2-Communities). The first implication of this is that finding a large community seems intractable. The second implication is that, since this is a hardness result for k = 2, the Uniform k-Communities problem is not fixed-parameter tractable when k is the parameter. (2) The second observation is that communities are not required to be connected in Olsen (2012)'s definition. However, we indicate that our result holds as well as the results by Olsen (2012) when we require communities to be connected, and we show examples where using connected communities seems more natural.

关键词： parameterized complexity graph partitioning complexity community detection

来源：评论

学校读者我要写书评

暂无评论

On the complexity of some colorful problems parameterized by treewidth

引用

INFORMATION AND COMPUTATION 2011年第2期209卷 143-153页

作者： Fellows, Michael R. Fomin, Fedor V. Lokshtanov, Daniel Rosamond, Frances Saurabh, Saket Szeider, Stefan Thomassen, Carsten Charles Darwin Univ Darwin NT Australia Univ Bergen Dept Informat Bergen Norway Univ Calif Berkeley Dept Comp Sci & Engn Berkeley CA 94720 USA Inst Math Sci Madras 600113 Tamil Nadu India Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Danish Tech Univ Math Inst Lyngby Denmark

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph. 1. The LIST COLORING problem takes as input a graph G. together with an assignment to each vertex v of a set of colors C-v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C-v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related PRECOLORING EXTENSION problem is also shown to be W[1]-hard, parameterized by treewidth. 2. An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, LIST EQUITABLE COLORING is W[1]-hard for forests, parameterized by the number of colors on the lists. 3. The list chromatic number chi(l)(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of C. of a list L-v of colors, where each list has length at least r, there is a choice of one color from each vertex list L-v yielding a proper coloring of G. We show that the problem of determining whether chi(l)(G) <= r, the LIST CHROMATIC NUMBER problem, is solvable in linear time on graphs of constant treewidth. (C) 2010 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Bounded treewidth Graph coloring

来源：评论

学校读者我要写书评

暂无评论

On Bounded-Degree Vertex Deletion parameterized by treewidth

引用

DISCRETE APPLIED MATHEMATICS 2012年第1-2期160卷 53-60页

作者： Betzler, Nadja Bredereck, Robert Niedermeier, Rolf Uhlmann, Johannes TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

Given an undirected graph G and an integer d >= 0, the NP-hard BOUNDED-DEGREE VERTEX DELETION problem asks to delete as few vertices as possible from G such that the resulting graph has maximum vertex degree d. Our main result is to prove that BOUNDED-DEGREE VERTEX DELETION is W[1]-hard with respect to the parameter treewidth. As a Side result, we obtain that the NP-hard VECTOR DOMINATING SET problem is W[1]-hard with respect to the parameter treewidth. On the positive side, we show that BOUNDED-DEGREE VERTEX DELETION becomes fixed-parameter tractable when parameterized by the combined parameter treewidth and number of vertices to delete, and when parametrized by the feedback edge set number. (C) 2011 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Structural parameterization Tree-likeness Vector Dominating Set k-dependent set co-k-plexes

来源：评论

学校读者我要写书评

暂无评论

On families of categorial grammars of bounded value, their learnability and related complexity questions

引用

THEORETICAL COMPUTER SCIENCE 2012年 452卷 21-38页

作者： Florencio, Christophe Costa Fernau, Henning Univ Amsterdam Inst Informat ILPS Amsterdam Netherlands Univ Trier FB 4 Abt Informat D-54286 Trier Germany

In Kanazawa (1998) [1], the learnability of several parameterized families of categorial grammar classes was studied. These classes were shown to be learnable in the technical sense of identifiability in the limit from positive data. They are defined in terms of bounds on parameters of the grammars which intuitively correspond to restrictions on linguistic aspects, such as the amount of lexical ambiguity. The time complexity of learning these classes has been studied in Costa Florncio (2003) [2]. It was shown that, for most of these classes, selecting a grammar from the class that is consistent with given data is NP-hard. In this paper existing complexity results are sharpened by demonstrating W[2]-hardness. Additionally, parameters are defined that allow FPT-results;roughly, this implies that if these parameters are fixed, these problems become tractable. We also define the new family G(k-sum-val), which is natural from the viewpoints of parameterized complexity, a flourishing area of complexity Theory (see Downey and Fellows (1999) [3]) and from Descriptional complexity, a sub-area of Formal Language Theory (see Holzer and Kutrib (2010) [4]). We prove its learnability, analyze its relation to other classes from the literature and prove a hierarchy theorem. This approach is then generalized to a parameterized family defined in terms of a bound on the descriptional complexity expressed as a Holder norm. We show that both the hierarchy result and the property of finite elasticity (and thus learnability) are preserved under this generalization. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Grammar induction Identification in the limit Finite elasticity parameterized complexity Categorial grammar Regular tree languages Holder norms

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for finding and counting subgraphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第3期78卷 698-706页

作者： Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket Rao, B. V. Raghavendra Univ Bergen Dept Informat N-5008 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India Univ Saarland Dept Comp Sci D-6600 Saarbrucken Germany

In the SUBGRAPH ISOMORPHISM problem we are given two graphs F and G on k and n vertices respectively as an input, and the question is whether there exists a subgraph of G isomorphic to F. We show that if the treewidth of F is at most t, then there is a randomized algorithm for the SUBGRAPH ISOMORPHISM problem running in time O*(2(k)(n(2t)). Our proof is based on a novel construction of an arithmetic circuit of size at most n(O)(t) for a new multivariate polynomial, Homomorphism Polynomial, of degree at most k, which in turn is used to solve the SUBGRAPH ISOMORPHISM problem. For the counting version of the SUBGRAPH ISOMORPHISM problem, where the objective is to count the number of distinct subgraphs of G that are isomorphic to F, we give a deterministic algorithm running oki in time and space O*(((n)(k/2))n(2p)) or ((n)(k/2))nO((tlogk)). We also give an algorithm running in time O*(2(k)((n)(k/2))n(5p)) and taking O*(n(p)) space. Here p and t denote the pathwidth and the treewidth of F, respectively. Our work improves on the previous results on SUBGRAPH ISOMORPHISM, it also extends and unifies most of the known results on sub-path and sub-tree isomorphisms. (C) 2011 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Subgraph Isomorphism Homomorphism Counting Treewidth

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：