Search

Abstract: We introduce the maximum common subgraph problem for multiple graphs (Multi-MCS) inspired by various biological applications such as multiple alignments of gene sequences, protein structures, metabolic pathways, or protein–protein interaction networks. Multi-MCS is a generalization of the two-graph Maximum Common Subgraph problem (MCS). On the basis of the framework of parameterized complexity theory, we derive the parameterized complexity of Multi-MCS for various parameters for different classes of graphs. For example, for directed graphs with labeled vertices, we prove that the parameterized -Multi-MCS problem is [2]-hard, while the parameterized -Multi-MCS problem is -hard (), where and are the size of the maximum common subgraph and the number of multiple graphs, respectively. We show similar results for other parameterized versions of the Multi-MCS problem for directed graphs with vertex labels and undirected graphs with vertex and edge labels by giving linear FPT reductions of the problems from parameterized versions of the longest common subsequence problem. Likewise, for unlabeled undirected graphs, we show that a parameterized version of the Multi-MCS problem with a fixed number of input graphs is [1]-complete by showing a linear FPT reduction to and from a parameterized version of the maximum clique problem. [Copyright &y& Elsevier]

Abstract: In this paper, we study the inapproximability of the following NP-complete number theoretic optimization problems introduced by Rössner and Seifert [C. Rössner, J.P. Seifert, The complexity of approximate optima for greatest common divisor computations, in: Proceedings of the 2nd International Algorithmic Number Theory Symposium, ANTS-II, 1996, pp. 307–322]: Given numbers , find an -minimum GCD multiplier for , i.e., a vector with minimum satisfying . We show that assuming , it is NP-hard to approximate the Minimum GCD Multiplier in norm () within a factor for some constant where is the dimension of the given vector. This improves on the best previous result. The best result so far gave factor hardness by Rössner and Seifert [C. Rössner, J.P. Seifert, The complexity of approximate optima for greatest common divisor computations, in: Proceedings of the 2nd International Algorithmic Number Theory Symposium, ANTS-II, 1996, pp. 307–322], where is an arbitrarily small constant. [Copyright &y& Elsevier]

Abstract: Let be any fixed real. We show that assuming , it is hard to approximate the Minimum Solutions of Linear Diophantine Equations in norm within any constant factor and it is also hard to approximate the Minimum Solutions of Linear Diophantine Equations in norm within the factor for some constant where is the number of variables in the equations. [Copyright &y& Elsevier]