Search

This special issue of Algorithms is devoted to the design and analysis of algorithms for solving combinatorial problems of a theoretical or practical nature involving graphs, with a focus on computational complexity.

Abstract: We present a new approach to the efficient solution of important computational problems that arise in the context of abstract argumentation. Our approach makes known algorithms defined for restricted fragments generally applicable, at a computational cost that scales with the distance from the fragment. Thus, in a certain sense, we gradually augment tractable fragments. Surprisingly, it turns out that some tractable fragments admit such an augmentation and that others do not. More specifically, we show that the problems of Credulous and Skeptical Acceptance are fixed-parameter tractable when parameterized by the distance from the fragment of acyclic argumentation frameworks—for most semantics. Other tractable fragments such as the fragments of symmetrical and bipartite frameworks seem to prohibit an augmentation: the acceptance problems are already intractable for frameworks at distance 1 from the fragments. For our study we use a broad setting and consider several different semantics. For the algorithmic results we utilize recent advances in fixed-parameter tractability. [Copyright &y& Elsevier]

Abstract: Abstract argumentation frameworks have received a lot of interest in recent years. Most computational problems in this area are intractable but several tractable fragments have been identified. In particular, Dunne showed that many problems can be solved in linear time for argumentation frameworks of bounded tree-width. However, these tractability results, which were obtained via Courcelleʼs Theorem, do not directly lead to efficient algorithms. The goal of this paper is to turn the theoretical tractability results into efficient algorithms and to explore the potential of directed notions of tree-width for defining larger tractable fragments. As a by-product, we will sharpen some known complexity results. [Copyright &y& Elsevier]

Abstract: The maximum independent set problem is known to be NP-hard for graphs in general, but is solvable in polynomial time for graphs in many special classes. It is also known that the problem is generally intractable from a parameterized point of view. A simple Ramsey argument implies the fixed-parameter tractability of the maximum independent set problem in classes of graphs of bounded clique number. Beyond this observation very little is known about the parameterized complexity of the problem in restricted graph families. In the present paper we develop fpt-algorithms for graphs in some classes extending graphs of bounded clique number. [Copyright &y& Elsevier]

Abstract: In this paper, we explore worst-case solutions for the problems of single and multiple matching on strings in the word-RAM model with word length w. In the first problem, we have to build a data structure based on a pattern p of length m over an alphabet of size σ such that we can answer to the following query: given a text T of length n, where each character is encoded using log σ bits return the positions of all the occurrences of p in T (in the following we refer by occ to the number of reported occurrences). For the multi-pattern matching problem we have a set S of d patterns of total length m and a query on a text T consists in finding all positions of all occurrences in T of the patterns in S. As each character of the text is encoded using log σ bits and we can read w bits in constant time in the RAM model, we assume that we can read up to consecutive characters of the text in one time step. This implies that the fastest possible query time for both problems is . In this paper we present several different results for both problems which come close to that best possible query time. We first present two different linear space data structures for the first and second problem: the first one answers to single pattern matching queries in time while the second one answers to multiple pattern matching queries to where y is the length of the shortest pattern. We then show how a simple application of the four Russian technique permits to get data structures with query times independent of the length of the shortest pattern (the length of the only pattern in case of single string matching) at the expense of using more space. [Copyright &y& Elsevier]

We introduce the NP-hard graph-based data clustering problem s- Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s−1 other vertices; cliques are 1-plexes. We propose a new method based on 'approximation and tidying' for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing 'approximation and tidying', we develop data reduction rules that, in O( ksn) time, transform an s- Plex Cluster Vertex Deletion instance with n vertices into an equivalent instance with O( k s) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method. [ABSTRACT FROM AUTHOR]

Abstract: We address in this paper a new computational biology problem that aims at understanding a mechanism that could potentially be used to genetically manipulate natural insect populations infected by inherited, intra-cellular parasitic bacteria. In this problem, that we denote by Mod/Resc Parsimony Inference, we are given a boolean matrix and the goal is to find two other boolean matrices with a minimum number of columns such that an appropriately defined operation on these matrices gives back the input. We show that this is formally equivalent to the Biclique Edge Cover for Bipartite Graphs problem and derive some complexity results for our problem using this equivalence. We provide a new, fixed-parameter tractability approach for solving both problems that slightly improves upon a previously published algorithm for the Biclique Edge Cover for Bipartite Graphs. Finally, we present experimental results applying some of our techniques to a real-life dataset. [Copyright &y& Elsevier]

Abstract: We present a first thorough theoretical analysis of the Transitivity Editing problem on digraphs. Herein, the task is to make a given digraph transitive by a minimum number of arc insertions or deletions. Transitivity Editing has applications in the detection of hierarchical structure in molecular characteristics of diseases. We demonstrate that if the input digraph does not contain “diamonds”, then there is an optimal solution that performs only arc deletions. This fact helps us construct a first proof of NP-hardness, which also extends to the restricted cases in which the input digraph is acyclic or has maximum degree three. By providing an -vertex problem kernel, we answer an open question from the literature. In case of digraphs with maximum degree d, an -vertex problem kernel can be shown. Moreover, we improve previous fixed-parameter algorithms, now achieving a running time of for an n-vertex digraph if k arc modifications are sufficient to make it transitive. Our hardness as well as algorithmic results transfer to Transitivity Deletion, where only arc deletions are allowed. [Copyright &y& Elsevier]

A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O( n)-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation. [ABSTRACT FROM AUTHOR]

Given n points, called terminals, in the plane ℝ and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ and a spanning tree on the n+ k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ, usually, the Euclidean or the L metric. This problem is known to be NP-hard. In this paper, we study this problem in the L metric for any 1≤ p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f( k)⋅ nlog n time for the L and the L metrics, and the first exact algorithm for the L metric for any fixed rational p with 1< p<∞ whose time complexity is f( k)⋅( n+ nlog n), where f( k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L metric. [ABSTRACT FROM AUTHOR]

Recently, numerous practical and theoretical studies in evolutionary biology aim at calculating the extent to which reticulation-for example, horizontal gene transfer, hybridization, or recombination-has influenced the evolution for a set of present-day species. It has been shown that inferring the minimum number of hybridization events that is needed to simultaneously explain the evolutionary history for a set of trees is an NP-hard and also fixed-parameter tractable problem. In this article, we give a new fixed-parameter algorithm for computing the minimum number of hybridization events for when two rooted binary phylogenetic trees are given. This newly developed algorithm is based on interleaving-a technique using repeated kernelization steps that are applied throughout the exhaustive search part of a fixed-parameter algorithm. To show that our algorithm runs efficiently to be applicable to a wide range of practical problem instances, we apply it to a grass data set and highlight the significant improvements in terms of running times in comparison to an algorithm that has previously been implemented. [ABSTRACT FROM AUTHOR]

Abstract: One prominent account of concept and category learning is that concepts and categories (jointly referred to as ‘generalizations’) are abstractions derived by extracting common analogical structure from sets of exemplars. This account enjoys considerable empirical support and has informed the design of models of learning in artificial intelligence. One aspect of the theory that has received little attention to date is the computational tractability of the processes that it postulates. In this paper, we assess the (in)tractability of analogy-based generalization using proof techniques from computational complexity theory. Our results reveal some unique computational challenges for analogy-based generalization, which it seems need to be addressed before the account can claim cognitive plausibility. [Copyright &y& Elsevier]

We study the parameterized complexity of the k-center problem on a given n-point set P in ℝd, with the dimension d as the parameter. We show that the rectilinear 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in O(n log n) time for any fixed dimension d. On the other hand, we show that this is unlikely to be the case with both the Euclidean and rectilinear k-center problems for any k ≥ 2 and k ≥ 4 respectively. In particular, we prove that deciding whether P can be covered by the union of 2 balls of given radius or by the union of 4 cubes of given side length is W[1]-hard with respect to d, and thus not fixed-parameter tractable unless FPT=W[1]. For the Euclidean case, we also show that even an no(d)-time algorithm does not exist, unless there is a 2o(n)-time algorithm for n-variable 3SAT, that is, the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

Abstract: We propose an effective polynomial-time preprocessing strategy for intractable median problems. Developing a new methodological framework, we show that if the input objects of generally intractable problems exhibit a sufficiently high degree of similarity between each other on average, then there are efficient exact solving algorithms. In other words, we show that the median problems Swap Median Permutation, Consensus Clustering, Kemeny Score, and Kemeny Tie Score all are fixed-parameter tractable with respect to the parameter “average distance between input objects”. To this end, we develop the novel concept of “partial kernelization” and, furthermore, identify polynomial-time solvable special cases for the considered problems. [Copyright &y& Elsevier]

The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques. We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of $\lvert V\rvert$ , where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying $k\leq25\lvert V\rvert$ . In addition to the fastest known fixed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modifications. For the first time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques. (A preliminary version of this paper appeared under the title 'Exact algorithms for cluster editing: Evaluation and experiments' in the Proceedings of the 7th Workshop on Experimental Algorithms, WEA 2008, in: LNCS, vol. 5038, Springer, pp. 289-302.) [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we deal with restoring missing information in molecule databases: Many data formats only store the atoms’ configuration but omit bond multiplicities. As this information is essential for various applications in chemistry, we consider the problem of recovering bond type information using a scoring function for the possible valences of each atom—the Bond Order Assignment problem. We show that the Bond Order Assignment is NP-hard, and its maximization version is MAX SNP-hard. We then give two exact fixed-parameter algorithms for the problem, where bond orders are computed via dynamic programming on a tree decomposition of the molecule graph. We evaluate our algorithm on a set of real molecule graphs and find that it works fast in practice. [Copyright &y& Elsevier]

Abstract: We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number . In the case of -vertex-overlap, each vertex may be part of at most  maximal cliques; -edge-overlap is analogously defined in terms of edges. We provide a complexity dichotomy (polynomial-time solvable versus NP-hard) for the underlying edge modification problems, develop forbidden subgraph characterizations of “cluster graphs with overlaps”, and study the parameterized complexity in terms of the number of allowed edge modifications, achieving fixed-parameter tractability (in case of constant -values) and parameterized hardness (in case of unbounded -values). [Copyright &y& Elsevier]

We introduce the S-PLEX CLUSTER EDITING problem as a generalization of the well-studied CLUSTER EDITING problem; both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is CLUSTER EDITING), the task in the case of S-PLEX CLUSTER EDITING is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least |S| -- s. Cliques are 1-plexes. The advantage of s-plexes for s ≥ 2 is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications; this is often a reasonable assumption under a maximum parsimony model for data clustering. [ABSTRACT FROM AUTHOR]

Abstract: We study the parameterized complexity of several minimum label graph problems, in which we are given an undirected graph whose edges are labeled, and a property Π, and we are asked to find a subset of edges satisfying property Π with respect to G that uses the minimum number of labels. These problems have a lot of applications in networking. We show that all the problems under consideration are W[2]-hard when parameterized by the number of used labels, and that they remain W[2]-hard even on graphs whose pathwidth is bounded above by a small constant. On the positive side, we prove that most of these problems are FPT when parameterized by the solution size, that is, the size of the sought edge set. For example, we show that computing a maximum matching or an edge dominating set that uses the minimum number of labels, is FPT when parameterized by the solution size. Proving that some of these problems are FPT requires interesting algorithmic methods that we develop in this paper. [ABSTRACT FROM AUTHOR]

It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f( k)⋅ n α for some constant α not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O( n k) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai (Discrete Appl. Math. 127:415–429, ). [ABSTRACT FROM AUTHOR]

Abstract: We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the NP-hard problem to delete a minimum number of rows or columns from a 0/1-matrix such that the remaining submatrix has the C1P. [Copyright &y& Elsevier]

Abstract: Given that most elementary problems in database design are NP-hard, the currently used database design algorithms produce suboptimal results. For example, the current 3NF decomposition algorithms may continue further decomposing a relation even though it is already in 3NF. In this paper we study database design problems whose sets of functional dependencies have bounded treewidth. For such sets, we develop polynomial-time and highly parallelizable algorithms for a number of central database design problems such as: [•] primality of an attribute; [•] 3NF-test for a relational schema or subschema; [•] BCNF-test for a subschema. In order to define the treewidth of a relational schema, we shall associate a hypergraph with it. Note that there are two main possibilities of defining the treewidth of a hypergraph : One is via the primal graph of and one is via the incidence graph of . Our algorithms apply to the case where the primal graph is considered. However, we also show that the tractability results still hold when the incidence graph is considered instead. It turns out that our results have interesting applications to logic-based abduction. By the well-known relationship with the primality problem in database design and the relevance problem in propositional abduction, our new algorithms and tractability results can be easily carried over from the former field to the latter. Moreover, we show how these tractability results can be further extended from propositional abduction to abductive diagnosis based on non-ground datalog. [Copyright &y& Elsevier]

Abstract: Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and improve fixed-parameter tractability results for these problems. We show that Feedback Vertex Set in tournaments (FVST) is amenable to the novel iterative compression technique, and we provide a depth-bounded search tree for Feedback Arc Set in bipartite tournaments based on a new forbidden subgraph characterization. Moreover, we apply the iterative compression technique to d-Hitting Set, which generalizes Feedback Vertex Set in tournaments, and obtain improved upper bounds for the time needed to solve 4-Hitting Set and 5-Hitting Set. Using our parameterized algorithm for Feedback Vertex Set in tournaments, we also give an exact (not parameterized) algorithm for it running in time, where n is the number of input graph vertices, answering a question of Woeginger [G.J. Woeginger, Open problems around exact algorithms, Discrete Appl. Math. 156 (3) (2008) 397–405]. [Copyright &y& Elsevier]

Cluster Editing is transforming a graph by at most k edge insertions or deletions into a disjoint union of cliques. This problem is fixed-parameter tractable (FPT). Here we compute concise enumerations of all minimal solutions in O(2.27 k+ k2 n+ m) time. Such enumerations support efficient inference procedures, but also the optimization of further objectives such as minimizing the number of clusters. In an extended problem version, target graphs may have a limited number of overlaps of cliques, measured by the number t of edges that remain when the twin vertices are merged. This problem is still in FPT, with respect to the combined parameter k and t. The result is based on a property of twin-free graphs. We also give FPT results for problem versions avoiding certain artificial clusterings. Furthermore, we prove that all solutions with minimal edit sequences differ on a so-called full kernel with at most k2/4+ O( k) vertices, that can be found in polynomial time. The size bound is tight. We also get a bound for the number of edges in the full kernel, which is optimal up to a (large) constant factor. Numerous open problems are mentioned. [ABSTRACT FROM AUTHOR]

Abstract: We show that the two NP-complete problems of Dodgson Score and Young Score have differing computational complexities when the winner is close to being a Condorcet winner. On the one hand, we present an efficient fixed-parameter algorithm for determining a Condorcet winner in Dodgson elections by a minimum number of switches in the votes. On the other hand, we prove that the corresponding problem for Young elections, where one has to delete votes instead of performing switches, is W[2]-complete. In addition, we study Dodgson elections that allow ties between the candidates and give fixed-parameter tractability as well as W[2]-completeness results depending on the cost model for switching ties. [Copyright &y& Elsevier]

Given a graph and terminal pairs (si, ti), i ϵ [k], the edge-disjoint paths problem is to determine whether there exist siti paths, i ϵ [k], that do not share any edges. We consider this problem on acyclic digraphs. It is known to be NP-complete and solvable in time nO(k) where n is the number of nodes. It has been a long-standing open question whether it is fixed-parameter tractable in k, i.e., whether it admits an algorithm with running time of the form f(k) nO(1). We resolve this question in the negative: we show that the problem is W[1]-hard, hence unlikely to be fixed-parameter tractable. In fact it remains W[1]-hard even if the demand graph consists of two sets of parallel edges. On a positive side, we give an O(m+kO(1) k! n) algorithm for the special case when G is acyclic and G+H is Eulerian, where H is the demand graph. We generalize this result (1) to the case when G+H is "nearly" Eulerian, and (2) to an analogous special case of the unsplittable flow problem, a generalized version of disjoint paths that has capacities and demands. [ABSTRACT FROM AUTHOR]

Abstract: Several forms of reasoning in AI – like abduction, closed world reasoning, circumscription, and disjunctive logic programming – are well known to be intractable. In fact, many of the relevant problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae or programs is bounded by some constant. Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction. [Copyright &y& Elsevier]

Abstract: The goal of the Cluster Editing problem is to make the fewest changes to the edge set of an input graph such that the resulting graph is a disjoint union of cliques. This problem is NP-complete but recently, several parameterized algorithms have been proposed. In this paper, we present a number of surprisingly simple search tree algorithms for Weighted Cluster Editing assuming that edge insertion and deletion costs are positive integers. We show that the smallest search tree has size for edit cost , resulting in the currently fastest parameterized algorithm, both for this problem and its unweighted counterpart. We have implemented and compared our algorithms, and achieved promising results. 1 [1] This is an extended version of two articles published in: Proc. of the 6th Asia Pacific Bioinformatics Conference, APBC 2008, in: Series on Advances in Bioinformatics and Computational Biology, vol. 5, Imperial College Press, pp. 211–220; and in: Proc. of the 2nd Conference on Combinatorial Optimization and Applications, COCOA 2008, in: LNCS, vol. 5038, Springer, pp. 289–302. [Copyright &y& Elsevier]

Abstract: We do computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques (“isolated maximal” vs “maximal isolated”). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter “degree of isolation”. We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks. [Copyright &y& Elsevier]

Abstract: The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a “consensus permutation” that is “closest” to the given set of permutations. Unfortunately, the problem is NP-hard. We provide a broad study of the parameterized complexity for computing optimal Kemeny rankings. Besides the three obvious parameters “number of votes”, “number of candidates”, and solution size (called Kemeny score), we consider further structural parameterizations. More specifically, we show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter “average pairwise Kendall–Tau distance ”. We describe a fixed-parameter algorithm with running time . Moreover, we extend our studies to the parameters “maximum range” and “average range” of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter “maximum range”, it becomes NP-complete in the case of an average range of two. This excludes fixed-parameter tractability with respect to the parameter “average range” unless P=NP. Finally, we extend some of our results to votes with ties and incomplete votes, where in both cases one no longer has permutations as input. [Copyright &y& Elsevier]

Abstract: Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial time brute force algorithm for finding a -element solution, we try to give algorithms with uniformly polynomial (i.e., ) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size , then we can determine in randomized time whether there is an independent set that is the union of blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a -element set in the intersection of matroids, or finding terminals in a network such that each of them can be connected simultaneously to the source by disjoint paths. [Copyright &y& Elsevier]

Abstract: In an undirected graph , a set of  vertices is called -isolated if it has less than  outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press)] gave an algorithm to enumerate all -isolated maximal cliques in  time. We extend this to enumerating all maximal -isolated cliques (which are a superset) and improve the running time bound to , using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to -plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the -plex is the parameter and a fixed-parameter algorithm for enumerating isolated -plexes when the parameter describes the degree of isolation. [Copyright &y& Elsevier]

Abstract: We investigate the Induced Subgraph Isomorphism problem with non-standard parameterization, where the parameter is the difference with and being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph , regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph representing the original pattern. We show fixed-parameter tractability of the cases where both and are planar and is 3-connected, or is a tree and is arbitrary. We also prove that the problem when and are both 3-connected planar graphs is NP-complete without parameterization. [Copyright &y& Elsevier]

Abstract: We study the parameterized complexity of the pseudo-achromatic number problem: Given an undirected graph and a parameter , determine if the graph can be partitioned into groups such that every two groups are connected by at least one edge. This problem has been extensively studied in graph theory and combinatorial optimization. We show that the problem has a kernel of at most vertices that is constructable in time , where and are the number of vertices and edges, respectively, in the graph, and is the parameter. This directly implies that the problem is fixed-parameter tractable. We also study generalizations of the problem and show that they are parameterized intractable. [Copyright &y& Elsevier]

Abstract: In the NP-hard Cluster Editing problem, we have as input an undirected graph and an integer . The question is whether we can transform , by inserting and deleting at most edges, into a cluster graph, that is, a union of disjoint cliques. We first confirm a conjecture by Michael Fellows [IWPEC 2006] that there is a polynomial-time kernelization for Cluster Editing that leads to a problem kernel with at most vertices. More precisely, we present a cubic-time algorithm that, given a graph and an integer , finds a graph and an integer such that can be transformed into a cluster graph by at most edge modifications iff can be transformed into a cluster graph by at most edge modifications, and the problem kernel has at most vertices. So far, only a problem kernel of vertices was known. Second, we show that this bound for the number of vertices of can be further improved to vertices. Finally, we consider the variant of Cluster Editing where the number of cliques that the cluster graph can contain is stipulated to be a constant . We present a simple kernelization for this variant leaving a problem kernel of at most vertices. [Copyright &y& Elsevier]

Abstract: We consider new parameterizations of NP-optimization problems that have nontrivial lower and/or upper bounds on their optimum solution size. The natural parameter, we argue, is the quantity above the lower bound or below the upper bound. We show that for every problem in MAX SNP, the optimum value is bounded below by an unbounded function of the input-size, and that the above-guarantee parameterization with respect to this lower bound is fixed-parameter tractable. We also observe that approximation algorithms give nontrivial lower or upper bounds on the solution size and that the above or below guarantee question with respect to these bounds is fixed-parameter tractable for a subclass of NP-optimization problems. We then introduce the notion of ‘tight’ lower and upper bounds and exhibit a number of problems for which the above-guarantee and below-guarantee parameterizations with respect to a tight bound is fixed-parameter tractable or W-hard. We show that if we parameterize “sufficiently” above or below the tight bounds, then these parameterized versions are not fixed-parameter tractable unless , for a subclass of NP-optimization problems. We also list several directions to explore in this paradigm. [Copyright &y& Elsevier]

A graph G is said to be a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs), and a cluster graph if G is a disjoint union of cliques (complete subgraphs). In this work, we study the parameterized versions of the NP-hard Bicluster Graph Editing and Cluster Graph Editing problems. The former consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an input bipartite graph. When at most k modifications are allowed ( Bicluster( k) Graph Editing problem), this problem is FPT, and can be solved in O(4 k nm) time by a standard search tree algorithm. We develop an algorithm of time complexity O(4 k + n+ m), which uses a strategy based on modular decomposition techniques; we slightly generalize the original problem as the input graph is not necessarily bipartite. The algorithm first builds a problem kernel with O( k 2) vertices in O( n+ m) time, and then applies a bounded search tree. We also show how this strategy based on modular decomposition leads to a new way of obtaining a problem kernel with O( k 2) vertices for the Cluster( k) Graph Editing problem, in O( n+ m) time. This problem consists of obtaining a cluster graph by modifying at most k edges in an input graph. A previous FPT algorithm of time O(1.92 k + n 3) for this problem was presented by Gramm et al. (Theory Comput. Syst. 38(4), 373–392, , Algorithmica 39(4), 321–347, ). In their solution, a problem kernel with O( k 2) vertices is built in O( n 3) time. [ABSTRACT FROM AUTHOR]

We study two pattern matching problems that are motivated by applications in computational biology. In the Closest Substring problem k strings s1,…, sk are given, and the task is to find a string s of length L such that each string si has a consecutive substring of length L whose distance is at most d from s. We present two algorithms that aim to be efficient for small fixed values of d and k: for some functions f and g, the algorithms have running time f(d) ∙ nO(log d) and g(d, k) ∙ nO(log log k), respectively. The second algorithm is based on connections with the extremal combinatorics of hypergraphs. The Closest Substring problem is also investigated from the parameterized complexity point of view. Answering an open question from [P. A. Evans, A. D. Smith, and H. T. Wareham, Theoret. Comput. Sci., 306 (2003), pp. 407-430, M. R. Fellows, J. Gramm, and R. Niedermeier, Combinatorica, 26 (2006), pp. 141-167, J. Gramm, J. Guo, and R. Niedermeier, Lecture Notes in Comput. Sci. 2751, Springer, Berlin, 2003, pp. 195-209, J. Gramm, R. Niedermeier, and P. Rossmanith, Algorithmica, 37 (2003), pp. 25-42], we show that the problem is W[1]-hard even if both d and k are parameters. It follows as a consequence of this hardness result that our algorithms are optimal in the sense that the exponent of n in the running time cannot be improved to o(log d) or to o(log log k) (modulo some complexity-theoretic assumptions). Consensus Patterns is the variant of the problem where, instead of the requirement that each si has a substring that is of distance at most d from si we have to select the substrings in such a way that the average of these k distances is at most d. By giving an f(δ) ∙ n9 time algorithm, we show that the problem is fixed-parameter tractable. This answers an open question from [M. R. Fellows, J. Gramm, and R. Niedermeier, Combinatorica, 26 (2006), pp. 141-167]. [ABSTRACT FROM AUTHOR]

Abstract: In the context of protein engineering, we consider the problem of computing an mRNA sequence of maximal codon-wise similarity to a given mRNA (and consequently, to a given protein) that additionally satisfies some secondary structure constraints, the so-called mRNA Structure Optimization (MRSO) problem. Since MRSO is known to be APX -hard, Bongartz [D. Bongartz, Some notes on the complexity of protein similarity search under mRNA structure constraints, in: Proc. of the 30th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2004, pp. 174–183] suggested to attack the problem using the approach of parameterized complexity. In this paper we propose three fixed-parameter algorithms that apply for several interesting parameters of MRSO. We believe these algorithms to be relevant for practical applications today, as well as for possible future applications. Furthermore, our results extend the known tractability borderline of MRSO, and provide new research horizons for further improvements of this sort. [Copyright &y& Elsevier]

Abstract: The NP-complete Closest 4-Leaf Power problem asks, given an undirected graph, whether it can be modified by at most  edge insertions or deletions such that it becomes a 4-leaf power. Herein, a 4-leaf power is a graph that can be constructed by considering an unrooted tree—the 4-leaf root—with leaves one-to-one labeled by the graph vertices, where we connect two graph vertices by an edge iff their corresponding leaves are at distance at most 4 in the tree. Complementing previous work on Closest 2-Leaf Power and Closest 3-Leaf Power, we give the first algorithmic result for Closest 4-Leaf Power, showing that Closest 4-Leaf Power is fixed-parameter tractable with respect to the parameter . [Copyright &y& Elsevier]

Abstract: In this paper the class of mixed Horn formulas is introduced that contain a Horn part and a 2-CNF (conjunctive normal form) (also called quadratic) part. We show that SAT remains NP-complete for such instances and also that any CNF formula can be encoded in terms of a mixed Horn formula in polynomial time. Further, we provide an exact deterministic algorithm showing that SAT for mixed Horn formulas containing n variables is solvable in time . A strong argument showing that it is hard to improve a time bound of for mixed Horn formulas is provided. We also obtain a fixed-parameter tractability classification for SAT restricted to mixed Horn formulas C of at most k variables in its positive 2-CNF part providing the bound . We further show that the NP-hard optimization problem minimum weight SAT for mixed Horn formulas can be solved in time if non-negative weights are assigned to the variables. Motivating examples for mixed Horn formulas are level graph formulas [B. Randerath, E. Speckenmeyer, E. Boros, P. Hammer, A. Kogan, K. Makino, B. Simeone, O. Cepek, A satisfiability formulation of problems on level graphs, ENDM 9 (2001)] and graph colorability formulas. [Copyright &y& Elsevier]

We initiate a systematic study of the ROW DELETION(B) problem on matrices: Given an input matrix A and a fixed "forbidden submatrix" B, the task is to remove a minimum number of rows from A such that no row or column permutation of B occurs as a submatrix in the resulting matrix. An application of this problem can be found, for instance, in the construction of perfect phylogenies. Establishing a strong connection to variants of the NP-complete HITTING SET problem, we describe and analyze structural properties of B that make ROW DELETION(B)NP-complete. On the positive side, the close relation with HITTING SET problems yields constant-factor polynomial-time approximation algorithms and fixed-parameter tractability results. [ABSTRACT FROM AUTHOR]

Abstract: We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite. [Copyright &y& Elsevier]

Abstract: We introduce an NP-complete special case of the Weighted Set Cover problem and show its fixed-parameter tractability with respect to the maximum subset size, a parameter that appears to be small in relevant applications. More precisely, in this practically relevant variant we require that the given collection C of subsets of a base set S should be “tree-like”. That is, the subsets in C can be organized in a tree T such that every subset one-to-one corresponds to a tree node and, for each element s of S, the nodes corresponding to the subsets containing s induce a subtree of T. This is equivalent to the problem of finding a minimum edge cover in an edge-weighted acyclic hypergraph. Our main result is an algorithm running in time where k denotes the maximum subset size, , and . The algorithm also implies a fixed-parameter tractability result for the NP-complete Multicut in Trees problem, complementing previous approximation results. Our results find applications in computational biology in phylogenomics and for saving memory in tree decomposition based graph algorithms. [Copyright &y& Elsevier]