Falk Hüffner

פאלק הופנר

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 O(1.709ⁿ) time, where n is the number of input graph vertices, answering a question of Woeginger [Discrete Appl. Math. 156(3):397–405, 2008].

Abstract. Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.

• Source code in Objective Caml

Abstract. We initiate the first systematic study of the NP-hard Cluster Vertex Deletion (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches for a minimum number of vertex deletions to transform a graph into a collection of disjoint cliques. The parameter is the number of vertex deletions. We present efficient fixed-parameter algorithms for CVD applying the fairly new iterative compression technique. Moreover, we study the variant of CVD where the maximum number of cliques to be generated is prespecified. Here, we exploit connections to fixed-parameter algorithms for (weighted) Vertex Cover.

Abstract. Given two binary phylogenetic trees covering the same n species, it is useful to compare them by drawing them with leaves arranged side-by-side. To facilitate comparison, we would like to arrange the trees to minimize the number of crossings k induced by connecting pairs of identical species. This is the NP-hard Tanglegram Layout problem. By providing a fast transformation to the Balanced Subgraph problem, we show that the problem admits an O(2^k n⁴) algorithm, improving upon a previous fixed-parameter approach with running time O(c^k n^O(1)) where c ≈ 1000. We enhance a Balanced Subgraph implementation based on data reduction and iterative compression with improvements tailored towards these instances, and run experiments with real-world data to show the practical applicability of this approach. All practically relevant (k ≤ 1000) Tanglegram Layout instances can be solved exactly within seconds. Additionally, we provide a kernel-like bound by showing how to reduce the Balanced Subgraph instances for Tanglegram Layout on complete binary trees to a size of O(k log k).

• Source code in Objective Caml

Abstract. In the network querying problem, one is given a protein complex or pathway of species A and a protein-protein interaction network of species B; the goal is to identify subnetworks of B that are similar to the query. Existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species A; however, in practice, this topology is often not known. To combat this problem, we develop a topology-free querying algorithm, which we call Torque. Given a query, represented as a set of proteins, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. The algorithm uses alternatively dynamic programming and integer linear programming for the search task. We test Torque with queries from yeast, fly, and human, where we compare it to the QNet topology-based approach, and with queries from less studied species, where only topology-free algorithms apply. Torque detects many more matches than QNet, while in both cases giving results that are highly functionally coherent.

• Web server for Torque

Abstract. Torque is a tool for cross-species querying of protein–protein interaction networks. It aims to answer the following question: given a set of proteins constituting a known complex or a pathway in one species, can a similar complex or pathway be found in the protein network of another species? To this end, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the target network, while allowing for both insertions and deletions. Unlike existing approaches, Torque does not require knowledge of the interconnections among the query proteins. It can handle large queries of up to 25 proteins.

• Web server for Torque

Abstract. We examine exact algorithms for the NP-hard Graph Bipartization problem. The task is, given a graph, to find a minimum set of vertices to delete to make it bipartite. Based on the “iterative compression” method introduced by Reed, Smith, and Vetta in 2004, we present new algorithms and experimental results. The worst-case time complexity is improved. Based on new structural insights, we give a simplified and more intuitive correctness proof. This also allows to establish a heuristic improvement that in particular speeds up the search on dense graphs. Our best algorithm can solve all instances from a testbed from computational biology within minutes, whereas established methods are only able to solve about half of the instances within reasonable time.

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 than 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 G_n,m,p 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).

Abstract. In an undirected graph G = (V, E), a set of k vertices is called c-isolated if it has less than c · k outgoing edges. Ito and Iwama [ACM Trans. Algorithms, to appear] gave an algorithm to enumerate all c-isolated maximal cliques in O(4^c · c⁴ · |E|) time. We extend this to enumerating all maximal c-isolated cliques (which are a superset) and improve the running time bound to O(2.89^c · c² · |E|), 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 s-plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s-plex is the parameter and a fixed-parameter algorithm for enumerating isolated s-plexes when the parameter describes the degree of isolation.

Abstract. Fixed-parameter algorithms can efficiently find optimal solutions to some NP-hard problems, including several problems that arise in graph-modeled data clustering. This survey provides a primer about practical techniques to develop such algorithms; in particular, we discuss the design of kernelizations (data reductions with provable performance guarantees) and depth-bounded search trees. Our investigations are circumstantiated by three concrete problems from the realm of graph-modeled data clustering for which fixed-parameter algorithms have been implemented and experimentally evaluated, namely Clique, Cluster Editing, and Clique Cover.

Abstract. The NP-hard Bicluster Editing is to add or remove at most k edges to make a bipartite graph a vertex-disjoint union of complete bipartite subgraphs. It has applications in the analysis of gene expression data. We show that by polynomial-time preprocessing, one can shrink a problem instance to one with 4k vertices, thus proving that the problem has a linear kernel, improving a quadratic kernel result. We further give a search tree algorithm that improves the running time bound from the trivial O(4^k + m) to O(3.24^k + m). Finally, we give a randomized 4-approximation, improving a known approximation with factor 11.

Abstract. We do computational studies concerning the enumeration of maximal 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 than for the enumeration of maximal general cliques and in filtering out cliques with special semantics. Our experiments cover synthetic graphs (G_n,m,p model) and financial networks; our results propose the enumeration of isolated cliques as a useful instrument in analyzing financial networks.

Abstract. We initiate the first systematic study of the NP-hard Cluster Vertex Deletion (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. Here one searches for a minimum number of vertex deletions to transform a graph into a collection of cliques. The parameter denotes the number of vertex deletions. We present several efficient fixed-parameter algorithms for CVD. Our iterative compression algorithm for CVD seems to be the first nontrivial application of this fairly new technique to a problem that is not a feedback set problem. Moreover, we study the variant of CVD where the number of cliques to be generated is prespecified. Here, we detect surprising connections to fixed-parameter algorithms for (Weighted) Vertex Cover.

Abstract. A vertex coloring of a tree is called convex if each color induces a connected component. The Convex Recoloring problem asks for a minimum-weight change of colors to achieve a convex coloring. For the non-uniformly weighted model, where the cost of changing a vertex v to color c depends on both v and c, we improve the running time on trees from O(Δ^κ · κn) to O(3^κ · κn), where Δ is the maximum vertex degree of the input graph G, κ is the number of colors, and n is the number of vertices in G. In the uniformly weighted case, where costs depend only on the vertex to be recolored, one can instead parameterize on the number of bad colors β ≤ κ, which is the number of colors that do not already induce a connected component. Here, we improve the running time from O(Δ^β · βn) to O(3^β · βn). The improvements come from a more fine-grained dynamic programming. For the case where the weights are integers bounded by M, using fast subset convolution, we further improve the running time with respect to the exponential part to O(2^κ · κ⁴n^2Mlog²(κnM)) and O(2^β · β⁴n^2M log²(βnM)) for the non-uniformly weighted and uniformly weighted model, respectively. Finally, we use fast subset convolution to improve the exponential part of the running time of the related 1-Connected Coloring Completion problem from O(8^k · k + 2^k · kn) to O(4^k · k⁴ log² k + 2^k · kn).

Abstract. The NP-complete Closest 4-Leaf Power problem asks, given an undirected graph, whether it can be modified by at most r 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 r.

Abstract. To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many applications. We develop for this problem efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques.

Abstract. Multicut is a fundamental network communication and connectivity problem. It is defined as: given an undirected graph and a collection of pairs of terminal vertices, find a minimum set of edges or vertices whose removal disconnects each pair. We mainly focus on the case of removing vertices, where we distinguish between allowing or disallowing the removal of terminal vertices. Complementing and refining previous results from the literature, we provide several NP-completeness and (fixed-parameter) tractability results for restricted classes of graphs such as trees, interval graphs, and graphs of bounded treewidth.

Abstract. The fixed-parameter approach is an algorithm design technique for solving combinatorially hard (mostly NP-hard) problems. For some of these problems, it can lead to algorithms that are both efficient and yet at the same time guaranteed to find optimal solutions. Focusing on their application to solving NP-hard problems in practice, we survey three main techniques to develop fixed-parameter algorithms, namely kernelisation (data reduction with provable performance guarantee), depth-bounded search trees, and a new technique called iterative compression. Our discussion is circumstantiated by several concrete case studies and provides pointers to various current challenges in the field.

Abstract. Color-coding is a technique to design fixed-parameter algorithms for several NP-complete subgraph isomorphism problems. Somewhat surprisingly, not much work has so far been spent on the actual implementation of algorithms that are based on color-coding, despite the elegance of this technique and its wide range of applicability to practically important problems. This work gives various novel algorithmic improvements for color-coding, both from a worst-case perspective as well as under practical considerations. We apply the resulting implementation to the identification of signaling pathways in protein interaction networks, demonstrating that our improvements speed up the color-coding algorithm by orders of magnitude over previous implementations. This allows more complex and larger structures to be identified in reasonable time; many biologically relevant instances can even be solved in seconds where, previously, hours were required.

• Source code in C++

Abstract. Fixed-parameter algorithms can efficiently find optimal solutions to some computationally hard (NP-hard) problems. We survey five main practical techniques to develop such algorithms. Each technique is circumstantiated by case studies of applications to biological problems. We also present other known bioinformatics-related applications and give pointers to experimental results.

Abstract. The Balanced Subgraph problem (edge deletion variant) asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. We present an exact algorithm for Balanced Subgraph based on a combination of data reduction rules and a fixed-parameter algorithm. The data reduction is based on finding small separators and a novel gadget construction scheme. The fixed-parameter algorithm is based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations [DasGupta et al., WEA 2006] were known.

• Source code in Objective Caml

Abstract. Color-coding is a technique to design fixed-parameter algorithms for several NP-complete subgraph-isomorphism problems. Somewhat surprisingly, not much work has so far been spent on the actual implementation of algorithms that are based on color-coding, despite the elegance of this technique and its wide range of applicability to practically important problems. This work gives various novel algorithmic improvements for color-coding, both from a worst-case perspective as well as under practical considerations. We apply the resulting implementation to the identification of signaling pathways in protein interaction networks, demonstrating that our improvements speed up the color-coding algorithm by orders of magnitude over previous implementations. This allows more complex and larger structures to be identified in reasonable time; many biologically relevant instances can even be solved in seconds where, previously, hours were required.

• Source code in C++

Abstract. In a graph G = (V,E), a vertex subset S⊆V of size k is called c-isolated if it has less than c·k outgoing edges. We repair a nontrivially flawed algorithm for enumerating all c-isolated cliques due to Ito et al. [ESA 2005] and obtain an algorithm running in O(4^c·c⁴·|E|) time. We describe a speedup trick that also helps 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 s-plexes (a relaxation of the clique notion), providing a W[1]-hardness result and a fixed-parameter algorithm for enumerating isolated s-plexes.

Abstract. Multiple pairwise comparisons are one of the most frequent tasks in applied statistics. In this context, letters displays may be used for a compact presentation of results of multiple comparisons. A heuristic previously proposed for this task is compared with two new algorithmic approaches. The latter rely on the equivalence of computing compact letters displays to computing clique covers in graphs, a problem that is well-studied in theoretical computer science. A thorough discussion of the three approaches aims to give a comparison of the algorithms' advantages and disadvantages. The three algorithms are compared in a series of experiments on simulated and real data, e.g., using data from wheat and triticale yield trials.

Abstract. The Feedback Arc Set problem asks whether it is possible to delete at most k arcs to make a directed graph acyclic. We show that Feedback Arc Set is NP-complete for bipartite tournaments, that is, directed graphs that are orientations of complete bipartite graphs.

Abstract. Faspad is a user-friendly tool that detects candidates for linear signaling pathways in protein interaction networks based on an approach by Scott et al. [Journal of Computational Biology, 2006]. Using recent algorithmic insights, it can solve the underlying NP-hard problem quite fast: For protein networks of typical size (several thousand nodes), pathway candidates of length up to 13 proteins can be found within seconds and with a 99.9% probability of optimality. Faspad graphically displays all candidates that are found; for evaluation and comparison purposes, an overlay of several candidates and the surrounding network context can also be shown.

• FASPAD for Linux (i386) or Windows (i386) and as source code

Abstract. This thesis is about the design, analysis, implementation, and experimental evaluation of algorithms for hard graph problems. The aim is to establish that the concept of fixed-parameter tractability, and in particular novel algorithmic techniques whose development was driven by this concept, can lead to practically useful programs for exactly solving real-world problem instances. In particular, we examine graph problems such as Clique Cover, Balanced Subgraph, and Minimum-Weight Path, which have applications in computational biology and other areas. We mainly use the techniques of data reduction, iterative compression, and color-coding. We develop a number of new fixed-parameter algorithms and give implementations for four important problems, all of which are to the best of our knowledge the currently fastest solvers.

Abstract. We initiate the study of the computational complexity of Matrix Robustness: Check whether deleting any k rows from a full-rank matrix does not change the matrix rank. This problem is motivated by applications in observability analysis of electrical power networks. We indicate the coNP-completeness of Matrix Robustness, provide linear programming based solutions (both exact and heuristic) and a problem-specific algorithm, and present encouraging experimental results.

Abstract. Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and partially improve fixed-parameter tractability results for these problems. We show that Feedback Vertex Set in tournaments is amenable to the novel iterative compression technique. Moreover, we provide data reductions and problem kernels for Feedback Vertex Set and Feedback Arc Set in tournaments, and a depth-bounded search tree for Feedback Arc Set in bipartite tournaments based on a new forbidden subgraph characterization.

Abstract. To cover the edges of a graph with a minimum number of cliques is an NP-complete problem with many applications. The state-of-the-art solving algorithm is a polynomial-time heuristic from the 1970's. We present an improvement of this heuristic. Our main contribution, however, is the development of efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques.

• Source code in Objective Caml

Abstract. The k-Leaf Root recognition problem is a particular case of graph power problems: For a given graph it asks whether there exists an unrooted tree—the k-leaf root—with leaves one-to-one labeled by the graph vertices and where the leaves have distance at mostk iff their corresponding vertices in the graph are connected by an edge. Here we study “error correction” versions of Leaf Root recognition—that is, adding or deleting at most l edges to generate a graph that has a k-leaf root. We provide several NP-completeness results in this context, and we show that the NP-complete Closest 3-Leaf Root problem (the error correction version of 3-Leaf Root) is fixed-parameter tractable with respect to the number of edge modifications or vertex deletions in the given graph. Thus, we provide the seemingly first nontrivial positive algorithmic results in the field of error compensation for leaf power problems with k > 2. To this end, as a result of independent interest, we develop a forbidden subgraph characterization of graphs with 3-leaf roots.

Abstract. Settling a ten years open question, we show that the NP-complete Feedback Vertex Set problem is deterministically solvable in O(c^k · m) time, where m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. As a second result, we present a fixed-parameter algorithm for the NP-complete Edge Bipartization problem with runtime O(2^k · m²).

Abstract. The NP-complete Closest 4-Leaf Power problem asks, given an undirected graph, whether it can be modified by at most l 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 and “completing” previous work on Closest 2-Leaf Power and Closest 3-Leaf Power, we show that Closest 4-Leaf Power is fixed-parameter tractable with respect to parameter l. This gives one of the first and so far deepest positive algorithmic results in the field of “approximate graph power recognition”—note that for 5-leaf powers even the complexity of the exact recognition problem is open.

Abstract. We examine exact algorithms for the NP-complete Graph Bipartization problem that asks for a minimum set of vertices to delete from a graph to make it bipartite. Based on the “iterative compression” method recently introduced by Reed, Smith, and Vetta, we present algorithmic improvements and experimental results. The worst-case time complexity is improved from O(3^k · kmn) to O(3^k · mn), where n is the number of vertices, m is the number of edges, and k is the number of vertices to delete. Our best algorithm can solve all problems from a testbed from computational biology within minutes, whereas established methods are only able to solve about half of the problems within reasonable time.

• Source code in C and benchmark instances

Abstract. We present efficient fixed-parameter algorithms for the NP-complete edge modification problems Cluster Editing and Cluster Deletion. Here, the goal is to make the fewest changes to the edge set of an input graph such that the new graph is a vertex-disjoint union of cliques. Allowing up to k edge additions and deletions (Cluster Editing), we solve this problem in O(2.27^k + |V|³) time; allowing only up to k edge deletions (Cluster Deletion), we solve this problem in O(1.77^k + |V|³) time. The key ingredients of our algorithms are two easy to implement bounded search tree algorithms and a reduction to a problem kernel of size O(k³). This improves and complements previous work. Finally, we discuss further improvements on search tree sizes using computer-generated case distinctions.

Abstract. Based on a series of known and new examples, we propose the generalized setting of “distance from triviality” measurement as a reasonable and prospective way of determining useful structural problem parameters in analyzing computationally hard problems. The underlying idea is to consider tractable special cases of generally hard problems and to introduce parameters that measure the distance from these special cases. In this paper we present several case studies of distance from triviality parameterizations (concerning Clique, Power Dominating Set, Set Cover, and Longest Common Subsequence) that exhibit the versatility of this approach to develop important new views for computational complexity analysis.

Abstract. We present a framework for an automated generation of exact search tree algorithms for NP-hard problems. The purpose of our approach is two-fold—rapid development and improved upper bounds. Many search tree algorithms for various problems in the literature are based on complicated case distinctions. Our approach may lead to a much simpler process of developing and analyzing these algorithms. Moreover, using the sheer computing power of machines it may also lead to improved upper bounds on search tree sizes (i.e., faster exact solving algorithms) in comparison with previously developed “hand-made” search trees. Among others, such an example is given with the NP-complete Cluster Editing problem (also known as Correlation Clustering on complete unweighted graphs), which asks for the minimum number of edge additions and deletions to create a graph which is a disjoint union of cliques. The hand-made search tree for Cluster Editing had worst-case size O(2.27^k), which now is improved to O(1.92^k) due to our new method. (Herein, k denotes the number of edge modifications allowed.)

• Source code in Objective Caml and C available on request

Abstract. We present a framework for the automated generation of exact searchtree algorithms for NP-hard problems. The purpose of our approach is two-fold: rapid development and improved upper bounds. Many search tree algorithms for various problems in the literature are based on complicated case distinctions. Our approach may lead to a much simpler process of developing and analyzing these algorithms. Moreover, using the sheer computing power of machines it can also provide improved upper bounds on search tree sizes (i.e., faster exact solving algorithms) in comparison with previously developed “hand-made” search trees. The generated search tree algorithms work by expanding a “window view” of the problem with local information, and then branch according to a precalculated rule for the resulting window. A central example in this work is given with the NP-complete Cluster Editing problem, which asks for the minimum number of edge additions and deletions in a graph to create a cluster graph (i.e., a graph which is a disjoint union of cliques). For Cluster Editing, a hand-made search tree is known with O(2.27^k) worst-case size, which is improved to O(1.92^k) due to our new method. (Herein, k denotes the number of edge modifications allowed.) A refinement of the search tree generator is presented, which tries to direct the expansion of the window towards advantageous case sets. The scheme is also successfully applied to several other graph modifications problems; generalizations to other problems are sketched.

• BibTeX bibliography data
• Source code in Objective Caml and C available on request

Abstract. We present first solutions of benchmark instances to the solitaire computer game Atomix found with different heuristic search methods. The problem is shown to be NP-hard. An implementation of the heuristic algorithm A* is presented that needs no priority queue, thereby having very low memory overhead. The limited memory algorithm IDA* is handicapped by the fact that, due to move transpositions, duplicates appear very frequently in the problem space; several schemes of using memory to mitigate this weakness are explored, among those “partial” schemes which trade memory savings for a small probability of not finding an optimal solution. Even though the underlying search graph is directed, backward search is shown to be viable, since the branching factor is the same as for forward search.

• BibTeX bibliography data
• atomix2fig.py, a Python script to convert Atomix levels from katomic to xfig format
• atomixer-2001.05.21.tar.gz, C++ source code of the solver