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

parameterized complexity in cognitive modeling: Foundations, applications and opportunities

COMPUTER JOURNAL 2008年第3期51卷 385-404页

作者： Van Rooij, Iris Wareham, Todd Radboud Univ Nijmegen Nijmegen Inst Cognit & Informat NL-6525 ED Nijmegen Netherlands Mem Univ Newfoundland Dept Comp Sci St John NF A1C 5S7 Canada

In cognitive science, natural cognitive processes are generally conceptualized as computational processes: they serve to transform sensory and mental inputs into mental and action outputs. At the highest level of abstraction, computational models of cognitive processes aim at specifying the computational problem computed by the process under study. Because computational problems are realistic cognitive models only insofar as they can plausibly be computed by the human brain given its limited resources for computation, computational tractability provides a useful constraint on cognitive models. In this paper, we consider the particular benefits of the parameterized complexity framework for identifying sources of intractability in cognitive models. We review existing applications of the parameterized framework to this end in the domains of perception, action and higher cognition. We further identify important opportunities and challenges for future research. These include the development of new methods for complexity analyses specifically tailored to the reverse engineering perspective underlying cognitive science.

关键词： cognitive modeling parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of cardinality constrained optimization problems

引用

COMPUTER JOURNAL 2008年第1期51卷 102-121页

作者： Cai, Leizhen Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

We study the parameterized complexity of cardinality constrained optimization problems, i.e. optimization problems that require their solutions to contain specified numbers of elements to optimize solution values. For this purpose, we consider around 20 such optimization problems, as well as their parametric duals, that deal with various fundamental relations among vertices and edges in graphs. We have almost completely settled their parameterized complexity by giving either FPT algorithms or W[1]-hardness proofs. Furthermore, we obtain faster exact algorithms for several cardinality constrained optimization problems by transforming them into problems of finding maximum (minimum) weight triangles in weighted graphs.

关键词： cardinality constrained optimization problem exact algorithm fixed-cardinality optimization problem graph problem parameterized complexity FPT algorithm W[1]-hardness

来源：评论

学校读者我要写书评

暂无评论

Pattern-Guided k-Anonymity

引用

ALGORITHMS 2013年第4期6卷 678-701页

作者： Bredereck, Robert Nichterlein, Andre Niedermeier, Rolf TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

We suggest a user-oriented approach to combinatorial data anonymization. A data matrix is called k-anonymous if every row appears at least k times-the goal of the NP-hard k-ANONYMITY problem then is to make a given matrix k-anonymous by suppressing (blanking out) as few entries as possible. Building on previous work and coping with corresponding deficiencies, we describe an enhanced k -anonymization problem called PATTERN-GUIDED k-ANONYMITY, where the users specify in which combinations suppressions may occur. In this way, the user of the anonymized data can express the differing importance of various data features. We show that PATTERN-GUIDED k-ANONYMITY is NP-hard. We complement this by a fixed-parameter tractability result based on a "data-driven parameterization" and, based on this, develop an exact integer linear program (ILP)-based solution method, as well as a simple, but very effective, greedy heuristic. Experiments on several real-world datasets show that our heuristic easily matches up to the established "Mondrian" algorithm for k-ANONYMITY in terms of the quality of the anonymization and outperforms it in terms of running time.

关键词： NP-hardness parameterized complexity integer linear programming exact algorithms heuristics experiments

来源：评论

学校读者我要写书评

暂无评论

Incremental list coloring of graphs, parameterized by conservation

引用

THEORETICAL COMPUTER SCIENCE 2013年 494卷 86-98页

作者： Hartung, Sepp Niedermeier, Rolf TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

Incrementally k-list coloring a graph means that a graph is given by adding vertices step by step, and for each intermediate step we ask for a vertex coloring such that each vertex has one of the colors specified by its associated list containing some of in total k colors. We introduce the "conservative version" of this problem by adding a further parameter c is an element of N specifying the maximum number of vertices to be recolored between two subsequent graphs (differing by one vertex). The "conservation parameter" c models the natural quest for a modest evolution of the coloring in the course of the incremental process instead of performing radical changes. We show that even on bipartite graphs the problem is NP-hard for k >= 3 and W[1]-hard for an unbounded number of colors when parameterized by c. In contrast, also on general graphs the problem becomes fixed-parameter tractable with respect to the combined parameter (k, c). We prove that the problem has an exponential-size kernel with respect to (k, c) and there is no polynomial-size kernel unless NP subset of coNP/poly. Furthermore, we investigate the parameterized complexity on various subclasses of perfect graphs. We show fixed-parameter tractability for the combined parameter treewidth and number k of colors. Finally, we provide empirical findings on the practical relevance of our approach in terms of an effective graph coloring heuristic. (c) 2013 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Data reduction Problem kernel Local search Incremental clustering Precoloring extension

来源：评论

学校读者我要写书评

暂无评论

complexity results for reconstructing binary images with disjoint components from horizontal and vertical projections

引用

DISCRETE APPLIED MATHEMATICS 2013年第15期161卷 2224-2235页

作者： Balazs, Peter Univ Szeged Dept Image Proc & Comp Graph H-6720 Szeged Hungary

The problem of reconstructing a special class of binary images from their horizontal and vertical projections is considered. We present a general framework for analyzing the worst case complexity of this task if the image consists of more than one pairwise disjoint component. Applying the presented technique we analyze the complexity of reconstructing canonical hv-convex binary images. We also present parameterized complexity results on general and so-called glued hv-convex images. Moreover, we study how our results are related to the reconstruction of permutation matrices from four projections. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Discrete tomography Disjoint components hv-convexity Permutation matrix Polynomial-time reconstruction parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the (Non-)Existence of Polynomial Kernels for P_l-Free Edge Modification Problems

引用

ALGORITHMICA 2013年第4期65卷 900-926页

作者： Guillemot, Sylvain Havet, Frederic Paul, Christophe Perez, Anthony Iowa State Univ Dept Comp Sci Ames IA 50011 USA Univ Nice Sophia Antipolis CNRS INRIA Sophia Antipolis France Univ Montpellier 2 LIRMM CNRS Montpellier France Univ Orleans LIFO Orleans France

Given a graph G=(V,E) and a positive integer k, an edge modification problem for a graph property I consists in deciding whether there exists a set F of pairs of V of size at most k such that the graph satisfies the property I . In the I edge-completion problem, the set F is constrained to be disjoint from E;in the I edge-deletion problem, F is a subset of E;no constraint is imposed on F in the I edge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171-176, 1996;Fellows et al. in FCT, pp. 312-321, 2007;Heggernes et al. in STOC, pp. 374-381, 2007). When parameterized by the size k of the set F, it has been proved that if I is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the three I edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171-176, 1996). It was then natural to ask (Bodlaender et al. in IWPEC, 2006) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance (G',k') with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlstrom answered this question negatively (Kratsch and Wahlstrom in IWPEC, pp. 264-275, 2009). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlstrom asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P (4)-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist f

关键词： parameterized complexity Kernelization algorithms Cograph Modular decomposition

来源：评论

学校读者我要写书评

暂无评论

Finding and Counting Vertex-Colored Subtrees

引用

ALGORITHMICA 2013年第4期65卷 828-844页

作者： Guillemot, Sylvain Sikora, Florian Univ Jena Lehrstuhl Bioinformat D-00743 Jena Germany Iowa State Univ Dept Comp Sci Ames IA 50011 USA Univ Paris Est LIGM CNRS UMR 8049 F-77454 Marne La Vallee 2 France

The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3(4):360-368, 2006) in the context of biological networks. The problem is to decide if a vertex-colored graph has a connected subgraph whose colors equal a given multiset of colors M. It is a graph pattern-matching problem variant, where the structure of the occurrence of the pattern is not of interest but the only requirement is the connectedness. Using an algebraic framework recently introduced by Koutis (Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5125, pp. 575-586, 2008) and Koutis and Williams (Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5555, pp. 653-664, 2009), we obtain new FPT algorithms for Graph Motif and variants, with improved running times. We also obtain results on the counting versions of this problem, proving that the counting problem is FPT if M is a set, but becomes #W[1]-hard if M is a multiset with two colors. Finally, we present an experimental evaluation of this approach on real datasets, showing that its performance compares favorably with existing software.

关键词： parameterized complexity Pattern matching in graphs Biological networks Vertex-colored graphs

来源：评论

学校读者我要写书评

暂无评论

STEINER FOREST ORIENTATION PROBLEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第3期27卷 1503-1513页

作者： Cygan, Marek Kortsarz, Guy Nutov, Zeev Univ Lugano IDSIA CH-6900 Lugano Switzerland Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA Open Univ Israel Raanana Israel

We consider connectivity problems with orientation constraints. Given a directed graph D and a collection of ordered node pairs P let P[D] = {(u, v) is an element of P : D contains a uv-path}. In the Steiner Forest Orientation problem we are given an undirected graph G = (V, E) with edge-costs and a set P subset of V x V of ordered node pairs. The goal is to find a minimum-cost subgraph H of G and an orientation D of H such that P[D] = P. We give a 4-approximation algorithm for this problem. In the Maximum Pairs Orientation problem we are given a graph G and a multicollection of ordered node pairs P on V. The goal is to find an orientation D of G such that P[D] is maximum. Generalizing the result of Arkin and Hassin [Discrete Appl. Math., 116 (2002), pp. 271-278] for vertical bar P vertical bar = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in n(O(|P|)) time whether G has an orientation D with P[D] = P. (For undirected graphs this problem admits a polynomial time algorithm for any P, but it is NP-complete on mixed graphs.) For undirected graphs, we will show that one can decide whether G admits an orientation D with vertical bar P[D]vertical bar >= k in O(n + m) + 2(O(k . log log k)) time;hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [Algorithms Molecular Biol., 6 (2011)]. We also show that Maximum Pairs Orientation admits ratio O(log vertical bar P vertical bar/log log vertical bar P vertical bar), which is better than the ratio O(log n/log log n) of Gamzu, Segev, and Sharan [Proceedings of WABI 2010, pp. 215-225] when vertical bar P vertical bar < n.

关键词： approximation algorithms graph algorithms graph orientation parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized Two-Player Nash Equilibrium

引用

ALGORITHMICA 2013年第4期65卷 802-816页

作者： Hermelin, Danny Huang, Chien-Chung Kratsch, Stefan Wahlstroem, Magnus Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Berlin Berlin Germany Univ Utrecht Utrecht Netherlands

We study the problem of computing Nash equilibria in a two-player normal form (bimatrix) game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in which the problem becomes fixed-parameter tractable. Our results are based on a graph-theoretic representation of a bimatrix game, and on applying graph-theoretic tools on this representation.

关键词： Two-player games Nash equilibrium parameterized complexity Algorithms

来源：评论

学校读者我要写书评

暂无评论

A linear vertex kernel for maximum internal spanning tree

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2013年第1期79卷 1-6页

作者： Fomin, Fedor V. Gaspers, Serge Saurabh, Saket Thomasse, Stephan Vienna Univ Technol Inst Informat Syst 184 3 Favoritenstr 9-11 A-1040 Vienna Austria Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India ENS LIP F-69364 Lyon 07 France

We present a polynomial time algorithm that for any graph G and integer k >= 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G(R) on at most 3k vertices and an integer k' such that G has a spanning tree with at least k internal vertices if and only if G(R) has a spanning tree with at least k' internal vertices. In other words, we show that the MAXIMUM INTERNAL SPANNING TREE problem parameterized by the number of internal vertices k has a 3k-vertex kernel. Our result is based on an innovative application of a classical min-max result about hypertrees in hypergraphs which states that "a hypergraph H contains a hypertree if and only if H is partition-connected." (c) 2012 Elsevier Inc. All rights reserved.

关键词： Algorithm Crown decomposition Kernelization parameterized complexity Preprocessing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：