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

Obtaining Matrices with the Consecutive Ones Property by Row Deletions

ALGORITHMICA 2015年第3期71卷 758-773页

作者： Narayanaswamy, N. S. Subashini, R. Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India

A binary matrix has the Consecutive Ones Property (COP) if there exists a permutation of columns that arranges the ones consecutively in all the rows. We consider the parameterized complexity of -COS-R (Consecutive Ones Submatrix by Row deletions) problem [9]: Given a matrix and a positive integer , decide whether there exists a set of at most rows of whose deletion results in a matrix with the COP. The closely related Interval Deletion problem has recently been shown to be FPT [6]. We show that -COS-R is fixed-parameter tractable and has the current best run-time of , which is associated with the Interval Deletion problem. We also introduce a closely related optimization problem called Min-ICPSA: For a finite sized universe the input consists of a family of pairs of sets;the aim is to find a minimum number of pairs of sets to discard from such that for each one of the remaining pairs, say , and for any two of the remaining pairs, indexed by , . We show that Min-ICPSA is computationally equivalent to the Vertex Cover problem. We also show that it is at least as hard as the Hamilton Path problem in undirected graphs, even when each vertical bar A(k)vertical bar = 2, 1 <= k <= n.

关键词： Consecutive ones property Consecutive ones submatrix parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the kernelization of ranking r-CSPs: Linear vertex-kernels for generalizations of FEEDBACK ARC SET and BETWEENNESS in tournaments

引用

DISCRETE APPLIED MATHEMATICS 2015年第1期186卷 214-225页

作者： Perez, Anthony Univ Orleans INSA Ctr Val Loire LIFO EA 4022 F-45067 Orleans France

An instance of a RANKING r-CONSTRAINT SATISFACTION PROBLEM (ranking r-CSP for short) consists of a ground set of vertices V, an arity r >= 2, a parameter k is an element of N and a constraint system c, where c is a function which maps rankings of r-sized sets S subset of V to {0,1}. The objective is to decide if there exists a ranking a of the vertices satisfying all but at most k constraints (i.e Sigma(S subset of V, vertical bar S vertical bar=r) C(sigma(S)) <= k). We mainly focus on dense instances, that is instances where the constraint system is defined for every r-sized subset S subset of V. Famous dense ranking r-CSPs include FEEDBACK ARC SET and BETWEENNESS in tournaments, two well-studied problems (Alon et al., 2009;Bessy et al., 2011;Karpinski and Schudy, 2010, 2011;Paul et al., 2011). We consider such problems from the kernelization viewpoint (Niedermeier, 2006). We prove that so-called p(r)-simply characterized ranking r-CSPs admit linear vertex-kernels whenever they admit constant-factor approximation algorithms. This implies that r-DENSE BETWEENNESS and r-DENSE TRANSITIVE FEEDBACK ARC SET, WO natural generalizations of the previously mentioned problems (Karpinski and Schudy, 2010, 2011), admit linear vertex-kernels. Moreover, we introduce another generalization of FEEDBACK ARC SET IN TOURNAMENTS, which does not fit the aforementioned framework. Based on techniques from Coppersmith (2006) we obtain a 5-approximation, and then provide a linear vertex-kernel for this problem as well. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Kernelization algorithms parameterized complexity Ranking CSP Dense instances

来源：评论

学校读者我要写书评

暂无评论

Most frugal explanations in Bayesian networks

引用

ARTIFICIAL INTELLIGENCE 2015年 218卷 56-73页

作者： Kwisthout, Johan Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav NL-6500 HE Nijmegen Netherlands

Inferring the most probable explanation to a set of variables, given a partial observation of the remaining variables, is one of the canonical computational problems in Bayesian networks, with widespread applications in AI and beyond. This problem, known as MAP, is computationally intractable (NP-hard) and remains so even when only an approximate solution is sought. We propose a heuristic formulation of the MAP problem, denoted as Inference to the Most Frugal Explanation (MFE), based on the observation that many intermediate variables (that are neither observed nor to be explained) are irrelevant with respect to the outcome of the explanatory process. An explanation based on few samples (often even a singleton sample) from these irrelevant variables is typically almost as good as an explanation based on (the computationally costly) marginalization over these variables. We show that while MFE is computationally intractable in general (as is MAP), it can be tractably approximated under plausible situational constraints, and its inferences are fairly robust with respect to which intermediate variables are considered to be relevant. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Bayesian abduction parameterized complexity Approximation Heuristics Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Obtaining split graphs by edge contraction

引用

THEORETICAL COMPUTER SCIENCE 2015年第Part1期607卷 60-67页

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

We study the parameterized complexity of the following SPLIT CONTRACTION problem: Given a graph G, and an integer k as parameter, determine whether G can be modified into a split graph by contracting at most k edges. We show that SPLIT CONTRACTION can be solved in FPT time 2(0(k2))n(5), but admits no polynomial kernel unless NP C coNP/poly. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Edge contraction Split graphs FPT algorithm Incompressibility

来源：评论

学校读者我要写书评

暂无评论

Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization

引用

ALGORITHMICA 2015年第3期71卷 566-580页

作者： Bonnet, Edouard Escoffier, Bruno Paschos, Vangelis Th Tourniaire, Emeric Univ Paris 09 PSL Res Univ LAMSADE CNRSUMR 7243 Paris France Univ Paris 06 Univ Sorbonne LIP6 UMR 7606 F-75005 Paris France CNRS LIP6 UMR 7606 F-75005 Paris France Inst Univ France Paris France

We study the parameterized complexity of a broad class of problems called "local graph partitioning problems" that includes the classical fixed cardinality problems as max -vertex cover, -densest subgraph, etc. By developing a technique that we call "greediness-for-parameterization", we obtain fixed parameter algorithms with respect to a pair of parameters , the size of the solution (but not its value) and , the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem.

关键词： parameterized complexity FPT Greedy Branching Local partitioning problems

来源：评论

学校读者我要写书评

暂无评论

Parameterizations of hitting set of bundles and inverse scope

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第4期29卷 847-858页

作者： Damaschke, Peter Chalmers Dept Comp Sci & Engn S-41296 Gothenburg Sweden

Hitting Set of Bundles generalizes the ordinary Hitting Set problem in the way that prescribed bundles of elements rather than single elements have to be put in a hitting set. The goal is to minimize the total number of distinct elements in the solution. First we prove that Hitting Set of Bundles, with the number of hyperedges and the solution size as parameter, is -complete. This contrasts to the to the corresponding parameterized Hitting Set version which is in FPT. Then we use this result to prove -hardness also for the Inverse Scope problem and some of its variants. This problem asks to identify small sets of chemical reactants being able to produce a given set of target compounds in a network of reactions. The problem has a graph-theoretic formulation as a reachability problem in directed graphs. On the positive side, we give an FPT algorithm where the parameter is the total number of compounds involved in the reactions.

关键词： Hitting set parameterized complexity W[i]-hardness Chemical reaction network

来源：评论

学校读者我要写书评

暂无评论

On finding optimal polytrees

引用

THEORETICAL COMPUTER SCIENCE 2015年 592卷 49-58页

作者： Gaspers, Serge Koivisto, Mikko Liedloff, Mathieu Ordyniak, Sebastian Szeider, Stefan Univ New S Wales Sydney NSW 2052 Australia NICTA Canberra ACT Australia Univ Helsinki FIN-00014 Helsinki Finland Univ Orleans Orleans France Masaryk Univ Brno 60200 Czech Republic Vienna Univ Technol Inst Informat Syst Vienna Austria

We study the NP-hard problem of finding a directed acyclic graph (DAG) on a given set of nodes so as to maximize a given scoring function. The problem models the task of inferring a probabilistic network from data, which has been studied extensively in the fields of artificial intelligence and machine learning. Several variants of the problem, where the output DAG is constrained in several ways, are NP-hard as well, for example when the DAG is required to have bounded in-degree, or when it is required to be a polytree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. In this paper, we generalize this polynomial-time result to polytrees that can be turned into a branching by deleting a constant number of arcs. Our algorithm stems from a matroid intersection formulation. As the order of the polynomial time bound depends on the number of deleted arcs, the algorithm does not establish fixed-parameter tractability when parameterized by that number. We show that certain additional constraints on the sought polytree render the problem fixed-parameter tractable. We contrast this positive result by showing that if we parameterize by the number of deleted nodes, a somewhat more powerful parameter, the problem is not fixed-parameter tractable, subject to a complexity-theoretic assumption. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Directed acyclic graphs Branchings Polytrees parameterized complexity Matroids Probabilistic networks

来源：评论

学校读者我要写书评

暂无评论

An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 275-279页

作者： Watel, Dimitri Weisser, Marc-Antoine Bentz, Cedric Barth, Dominique SUPELEC Syst Sci Dept Comp Sci F-91192 Gif Sur Yvette France CEDRIC CNAM F-75141 Paris France Univ Versailles F-78035 Versailles France

Given a directed graph with n nodes, a root r, a set X of k nodes called terminals and non-negative weights omega over the arcs, the Directed Steiner Tree problem (DST) asks for a directed tree T* of minimum cost omega(T*) rooted at r and spanning X. If this problem has several applications in multicast routing in packet switching networks, the modeling is no longer adapted in networks based upon the circuit switching principle, in which some nodes, called non-diffusing nodes, are not able to duplicate packets. We study a generalization of DST, called Directed Steiner Tree with Limited number of Diffusing nodes (DSTLD), able to model the multicast routing in a network containing at most d diffusing nodes. We provide an FPT exact algorithm running in time O (t(d) . d(k) . n . (d + k)) and in polynomial space for DSTLD, where t(d) is the number of unordered rooted trees with d unlabelled nodes. Thereby, we also provide the first exact algorithm running in polynomial space and in FPT time with respect to k which returns an optimal solution for DST instead of the optimal cost only. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Directed Steiner Tree parameterized complexity Dynamic programming Algorithms Combinatorial problems

来源：评论

学校读者我要写书评

暂无评论

Kernelization lower bound for Permutation Pattern Matching

引用

INFORMATION PROCESSING LETTERS 2015年第5期115卷 527-531页

作者： Bliznets, Ivan Cygan, Marek Komosa, Pawel Mach, Lukas Russian Acad Sci St Petersburg Dept VA Steklov Math Inst Moscow 117901 Russia Univ Warsaw Inst Informat PL-00325 Warsaw Poland Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

A permutation pi contains a permutation a as a pattern if it contains a subsequence of length la vertical bar sigma vertical bar whose elements are in the same relative order as in the permutation a. This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption NP not subset of co-NP/poly) by introducing a new polynomial reduction from the clique problem to permutation pattern matching. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Algorithms parameterized complexity Polynomial kernels

来源：评论

学校读者我要写书评

暂无评论

On the complexity of finding a largest common subtree of bounded degree

引用

THEORETICAL COMPUTER SCIENCE 2015年 590卷 2-16页

作者： Akutsu, Tatsuya Tamura, Takeyuki Melkman, Avraham A. Takasu, Atsuhiro Kyoto Univ Inst Chem Res Bioinformat Ctr Uji Kyoto 6110011 Japan Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Natl Inst Informat Tokyo 1018430 Japan

The largest common subtree problem is to find a bijective mapping between subsets of nodes of two input rooted trees of maximum cardinality or weight that preserves labels and ancestry relationship. The problem is known to be NP-hard for unordered trees. In this paper, we consider a restricted unordered case in which the maximum outdegree of a common subtree is bounded by a constant D. We present an O(n(D)) time algorithm where n is the maximum size of two input trees, which improves a previous O(n(2D)) time algorithm. We also present an O((H-2 center dot 2(2H-1)center dot D-2H)(D-1) poly(n)) time algorithm, where H is the maximum height of two input trees. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Tree edit distance Unordered trees Dynamic programming parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：