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

On the parameterized complexity of the problem of inferring protein-protein interaction directions based on cause-effect pairs

引用

NETWORK MODELING AND ANALYSIS IN HEALTH INFORMATICS AND BIOINFORMATICS 2019年第1期8卷 11页

作者： Roayaei, Mehdy Tarbiat Modares Univ Tehran Iran

We consider the following problem: given an undirected (mixed) network and a set of ordered source-target pairs, or cause-effect pairs, direct all edges so as to maximize the number of pairs that admit a directed source-target path. This is called the maximum graph orientation problem, and has applications in understanding interactions in protein-protein interaction networks. Since this problem is NP-hard, we take the parameterized complexity viewpoint and study the parameterized (in)tractability of the problem with respect to various parameters on both undirected and mixed networks. In the undirected case, we determine the parameterized complexity of the problem (for non-fixed and fixed paths) with respect to the number of satisfied pairs. Also, we present an exact algorithm which outperforms the previous algorithms on trees with bounded number of leaves. In the mixed case, we present polynomial-time algorithms for the problem on paths and cycles, and an FPT algorithm with respect to the combined parameter number of arcs and number of pairs on general graphs.

关键词： Protein-protein interaction network Cause-effect pairs parameterized complexity Fixed-parameter tractable W[1]-hardness

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of non-monotonic logics

引用

ARCHIVE FOR MATHEMATICAL LOGIC 2015年第5-6期54卷 685-710页

作者： Meier, Arne Schindler, Irina Schmidt, Johannes Thomas, Michael Vollmer, Heribert Leibniz Univ Hannover Inst Theoret Informat Appelstr 4 D-30167 Hannover Germany Linkoping Univ Dept Comp & Informat Sci S-58183 Linkoping Sweden

We investigate the application of Courcelle's theorem and the logspace version of Elberfeld et al. in the context of non-monotonic reasoning. Here we formalize the implication problem for propositional sets of formulas, the extension existence problem for default logic, the expansion existence problem for autoepistemic logic, the circumscriptive inference problem, as well as the abduction problem in monadic second order logic and thereby obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu, resp., XLnu) under standard complexity assumptions.

关键词： Abduction Autoepistemic logic Default logic Circumscription parameterized complexity Courcelle's theorem Monadic second order logic

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of counting problems

引用

SIAM JOURNAL ON COMPUTING 2004年第4期33卷 892-922页

作者： Flum, J Grohe, M Univ Freiburg Inst Math Log D-79104 Freiburg Germany Humboldt Univ Inst Informat D-10099 Berlin Germany

We develop a parameterized complexity theory for counting problems. As the basis of this theory, we introduce a hierarchy of parameterized counting complexity classes #W[t], for t greater than or equal to 1, that corresponds to Downey and Fellows's W-hierarchy [R. G. Downey and M. R. Fellows, parameterized complexity, Springer-Verlag, New York, 1999] and we show that a few central W-completeness results for decision problems translate to #W-completeness results for the corresponding counting problems. Counting complexity gets interesting with problems whose decision version is tractable, but whose counting version is hard. Our main result states that counting cycles and paths of length k in both directed and undirected graphs, parameterized by k, is #W[1]-complete. This makes it highly unlikely that these problems are fixed-parameter tractable, even though their decision versions are fixed-parameter tractable. More explicitly, our result shows that most likely there is no f(k) . n(c)-algorithm for counting cycles or paths of length k in a graph of size n for any computable function f : N --> N and constant c, even though there is a 2(O(k)) . n(2.376) algorithm for finding a cycle or path of length k [N. Alon, R. Yuster, and U. Zwick, J. ACM, 42 (1995), pp. 844-856].

关键词： counting complexity parameterized complexity paths and cycles descriptive complexity

来源：评论

学校读者我要写书评

暂无评论

MATRIX RIGIDITY FROM THE VIEWPOINT OF parameterized complexity

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第2期32卷 966-985页

作者： Fomin, Fedor, V Lokshtanov, Daniel Meesum, S. M. Saurabh, Saket Zehavi, Meirav Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Theoret Comp Sci Madras 600113 Tamil Nadu India

For a target rank r, the rigidity of a matrix A over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in computational complexity theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of parameterized complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of parameterized complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in the case F = R or F is any finite field, this problem is fixed-parameter tractable with respect to k+ r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in real algebraic geometry, which are not well known in parameterized complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.

关键词： matrix rigidity parameterized complexity linear algebra

来源：评论

学校读者我要写书评

暂无评论

Taxi-sharing: parameterized complexity and approximability of the dial-a-ride problem with money as an incentive

引用

THEORETICAL COMPUTER SCIENCE 2018年 745卷 202-223页

作者： Watel, Dimitri Faye, Alain ENSIIE 1 Sq Resistance F-91025 Evry France Telecom SudParis SAMOVAR 9 Rue Charles Fourier F-91000 Evry France CNAM CEDRIC 2 Rue Conte F-75003 Paris France

We study, in this paper, a taxi-sharing problem, called Dial-a-Ride problem with money as an incentive (DARP-M). This problem consists in defining a set of taxis that will be shared by different clients in order to reduce their bill by a given factor alpha < 1. To achieve this, each client shares the cost of the ride with other passengers. More precisely, the fragments of the ride in which the client is alone is fully paid by this client and, for each fragment in which the client shares the taxi with other passengers, the cost is equally divided between the passengers. In addition to this cost constraint, the taxi must satisfy a time window constraint for each passenger and a capacity constraint. We define three versions of the problem: max-DARP-M where the objective is to drive the maximum number of clients with an arbitrarily large number of taxis;max-1-DARP-M in which we want to drive the maximum number of clients with one taxi;and 1-DARPM which consists in deciding whether it is possible to drive at least one client while satisfying the constraints. We study the parameterized complexity and approximability of those problems with respect to four parameters: the factor alpha, the capacity capa of the taxis, the maximum size TW of the time windows of the clients, and the value S of an optimal solution. Among other results, we prove that 1-DARP-M is NP-Complete and max-DARP-M and max-l-DARP-M cannot be approximated in polynomial time to within any variable ratio even if alpha, capa and T W are fixed and if the road network is a planar graph. We also give a polynomial algorithm for max-1-DARP-M for the case where capa and TW are fixed and where the network does not contain a circuit. This algorithm implies a 1/root n-polynomial approximation for max-DARP-M. (C) 2018 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Approximability Dial-a-ride problem Taxi-sharing

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of Guarding Almost Convex Polygons

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2024年第2期71卷 358-398页

作者： Agrawal, Akanksha Knudsen, Kristine V. K. Lokshtanov, Daniel Saurabh, Saket Zehavi, Meirav Indian Inst Technol Madras Chennai India Univ Bergen Bergen Norway Univ Calif Santa Barbara Santa Barbara CA 93106 USA Inst Math Sci Chennai India Ben Gurion Univ Negev IL-84105 Beer Sheva Israel

The ART GALLERY problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k;the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of ART GALLERY, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries dwere made: the above mentioned variants of ART GALLERY are all W[1]-hard with respect to k [Bonnet and Miltzowin 24thAnnual European Symposium onAlgorithms (Aarhus 2016)], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow in 33rd International Symposium on Computational Geometry (Brisbane 2017)], and it may require irrational guards [Abrahamsen et al. in 33rd International Symposium on Computational Geometry (Brisbane 2017)]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be.R-complete [Abrahamsen et al. in 50th Annual ACMSIGACT Symposium on Theory ofComputing (LosAngeles 2018)]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)]: Is ART GALLERY FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called VERTEX-VERTEX ART GALLERY. Apart from being a variant of ART GALLERY, this case can also be viewed as the classic DOMINATING SET problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos

关键词： Art gallery Reflex vertices Monotone 2-CSP parameterized complexity Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the median and closest problems under some permutation metrics

引用

ALGORITHMS FOR MOLECULAR BIOLOGY 2024年第1期19卷 1-18页

作者： Cunha, Luis Sau, Ignasi Souza, Ueverton Univ Fed Fluminense Inst Comp Niteroi Brazil Inst Matematica Pura & Aplicada IMPA Rio De Janeiro Brazil Univ Montpellier LIRMM CNRS Montpellier France

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. On the other hand, finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations of distinct integers, some distance metrics have been extensively studied. We investigate the median and closest problems on permutations over the following metrics: breakpoint distance, swap distance, block-interchange distance, short-block-move distance, and transposition distance. In biological applications some values are usually very small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation regarding some metrics of distance, even for only k=3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 3$$\end{document} permutations;Polynomial kernels for the problems of finding the median

关键词： Median problem Closest problem Genome rearrangements parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Discrete Morse Theory

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2016年第1期42卷 6-6页

作者： Burton, Benjamin A. Lewiner, Thomas Paixao, Joao Spreer, Jonathan Univ Queensland Sch Math & Phys Brisbane Qld 4072 Australia Pontificia Univ Catolica Rio de Janeiro Dept Matemat Rua Marques Sao Vicente 225 BR-22451900 Rio De Janeiro RJ Brazil Univ Fed Rio de Janeiro Dept Ciencia Computacao BR-21941 Rio De Janeiro Brazil

Optimal Morse matchings reveal essential structures of cell complexes that lead to powerful tools to study discrete geometrical objects, in particular, discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds through a reduction to the erasability problem. Here, we refine the study of the complexity of problems related to discrete Morse theory in terms of parameterized complexity. On the one hand, we prove that the erasability problem is W[P]-complete on the natural parameter. On the other hand, we propose an algorithm for computing optimal Morse matchings on triangulations of 3-manifolds, which is fixed-parameter tractable in the treewidth of the bipartite graph representing the adjacency of the 1- and 2-simplices. This algorithm also shows fixed-parameter tractability for problems such as erasability and maximum alternating cycle-free matching. We further show that these results are also true when the treewidth of the dual graph of the triangulated 3-manifold is bounded. Finally, we discuss the topological significance of the chosen parameters and investigate the respective treewidths of simplicial and generalized triangulations of 3-manifolds.

关键词： Algorithms Theory Alternating cycle-free matching collapsibility computational topology discrete Morse theory erasability fixed-parameter tractability parameterized complexity treewidth W[P]-completeness

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Elimination Distance to First-Order Logic Properties

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2022年第3期23卷 17-17页

作者： Fomin, Fedor, V Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Montpellier CNRS LIRMM 161 Rue Ada F-34095 Montpellier 5 France

The elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problem's fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: For every graph property P expressible by a first order-logic formula phi is an element of Sigma(3), that is, of the form phi = there exists x(1)there exists x(2) ... there exists x(r) for all y(1)for all y(2) ... for all y(s) there exists z(1)there exists z(2) ... there exists z(t) psi, where psi is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Sigma(3) include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulaswith even slightly more expressive prefix structure: There are formulas phi epsilon Pi(3), for which computing elimination distance is W[2]-hard.

关键词： First-order logic elimination distance parameterized complexity descriptive complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：