Falk Hüffner

Automated Search Tree Generation (2004; Gramm, Guo, Hüffner, Niedermeier) (2009)

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...

Falk Hüffner, Entry Rolf Niedermeier

development and analysis of algorithms.

Journal of Combinatorial Optimization manuscript No. (will be inserted by the editor) Separator-Based Data Reduction for Signed Graph Balancing (2009)

Falk Hüffner, Nadja Betzler, Rolf Niedermeier

the date of receipt and acceptance should be inserted later Abstract Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced...

Error compensation in leaf power problems (2009)

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier

The k-Leaf Power 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...

Closest 4-Leaf Power is Fixed-Parameter Tractable ⋆ (2009)

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

Torque: topology-free querying of protein interaction networks (2009)

Bruckner, Sharon, Hüffner, Falk, Karp, Richard M., Shamir, Ron, Sharan, Roded

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...

Communicated by: (2009)

Falk Hüffner, D. Wagner

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...

Speeding up Dynamic Programming for Some NP-hard Graph Recoloring Problems (2008)

Oriana Ponta, Falk Hüffner, Rolf Niedermeier

Abstract. A vertex coloring of a tree is called convex if each color induces a connected component. The NP-hard Convex Recoloring problem on vertex-colored trees asks for a minimum-weight change of...

Algorithms and Experiments for Parameterized Approaches to Hard Graph Problems (2008)

Hüffner, Falk

Many combinatorial problems that come up in the real world have been classified as NP-hard [Garey and Johnson 1979]. An example is the following task: After a series of experiments, certain pairs of...

doi:10.1093/comjnl/bxm040 Techniques For Practical Fixed-Parameter Algorithms (2008)

Fixed-Parameter Algorithms for Cluster Vertex Deletion (2008)

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...

Falk Hüffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier

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...

Algorithm Engineering for Optimal (2008)

Graph Bipartization, Falk Hüffner

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...

Complexity and exact algorithms for multicut (2008)

Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, Johannes Uhlmann

Abstract. The Multicut problem 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...

Matrix Robustness, with an Application to Power System Observability (2008)

Matthias Brosemann, Jochen Alber, Falk Hüffner, Rolf Niedermeier

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...

Optimal Edge Deletions for Signed Graph Balancing ⋆ (2008)

Falk Hüffner, Nadja Betzler, Rolf Niedermeier

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,...

Error compensation in leaf power problems (2008)

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier

The k-Leaf Power 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...

Complexity and exact algorithms for multicut (2008)

Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, Johannes Uhlmann

Abstract. The Multicut problem 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...

Fixed-Parameter Algorithms for Graph-Modeled Data Clustering (2008)

Minimum-Weight Path Minimum-Weight Path experiments Balanced Subgraph Balanced Subgraph experiments (2008)

Fixed-parameter algorithms can efficiently find optimal solutions to some NP-hard problems, including several problems that arise in graphmodeled data clustering. This survey provides a primer about...

Hard Graph Problems, Falk Hüffner, Nadja Betzler, Rolf Niedermeier, Sebastian Wernicke, Thomas Zichner, ...

Application: protein interaction networks

Algorithm Engineering for Optimal (2008)

Graph Bipartization, Falk Hüffner

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...

Feedback Arc Set in Bipartite Tournaments is NP-Complete (2008)

Jiong Guo, Falk Hüffner, Hannes Moser

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 NPcomplete for bipartite tournaments, that is,...

Developing Fixed-Parameter Algorithms to Solve Combinatorially Explosive Biological Problems (2008)

Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection ∗ (2008)

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...

Falk Hüffner, Sebastian Wernicke, Thomas Zichner

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...

Data Reduction and Exact Algorithms for Clique (2008)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

Matrix Robustness, with an Application to Power System Observability (2008)

Matthias Brosemann, Jochen Alber, Falk Hüffner, Rolf Niedermeier

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...

Techniques for Practical Fixed-Parameter Algorithms (2008)

Hüffner, Falk, Niedermeier, Rolf, Wernicke, Sebastian

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...

Fixed-Parameter Algorithms for Cluster Vertex Deletion (2008)

Falk Hüffner, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier

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...

Closest Strings, Primer Design, and Motif Search (2007)

Jens Gramm, Falk Hüffner, Rolf Niedermeier

Introduction CLOSEST STRING Given: k strings from # and a positive integer d. Question: Find a "closest string" s such that none of the given strings has Hamming distance greater than d to...

Graph Modification Problems and Automated Search Tree Generation (2007)

Falk Hüffner, Betreuer Pd, Dr. Rolf Niedermeier, Nwg Theoretische

We present a framework for the 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.

FASPAD: fast signaling pathway detection (2007)

Hüffner, Falk, Wernicke, Sebastian, Zichner, Thomas

Summary: 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,...

Algorithm engineering for colorcoding to facilitate signaling pathway detection (2007)

Techniques for Practical Fixed-Parameter Algorithms (2007)

To identify linear signaling pathways, Scott et al. [RECOMB, 2005] recently proposed to extract paths with high interaction probabilities from protein interaction networks. They used an algorithmic...

Various isolation concepts for the enumeration of dense subgraphs (2007)

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...

Christian Komusiewicz, Falk Hüffner, Hannes Moser, Rolf Niedermeier

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...

Algorithm engineering for colorcoding to facilitate signaling pathway detection (2007)

Data reduction, exact, and heuristic algorithms for clique cover (2006)

To identify linear signaling pathways, Scott et al. [RECOMB, 2005] recently proposed to extract paths with high interaction probabilities from protein interaction networks. They used an algorithmic...

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

Fixed-parameter tractability results for feedback set problems in tournaments (2006)

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truß

Abstract. Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and partially improve...

Data reduction, exact, and heuristic algorithms for clique cover (2006)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

Data reduction, exact, and heuristic algorithms for clique cover (2006)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

Fixed-parameter tractability results for feedback set problems in tournaments (2006)

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truß

Abstract. Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and partially improve...

Data reduction, exact, and heuristic algorithms for clique cover (2006)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

Algorithms for compact letter displays: Comparison and evaluation, Computational Statistics & Data Analysis (2006)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier B, Hans-peter Piepho, Ramona Schmid

Multiple pairwise comparisons are one of the most frequent tasks in applied statistics. In this context, letter displays may be used for a compact presentation of results of multiple comparisons. A...

Improved Fixed-Parameter Algorithms for Two Feedback Set Problems (2005)

Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, Sebastian Wernicke

Abstract. Settling a ten years open question, we show that the NPcomplete Feedback Vertex Set problem is deterministically solvable in O(c k ·m) time, where m denotes the number of graph edges, k...

Extending the tractability border for closest leaf powers (2005)

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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....

Improved Fixed-Parameter Algorithms for Two Feedback Set Problems (2005)

Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, Sebastian Wernicke

Abstract. Settling a ten years open question, we show that the NPcomplete Feedback Vertex Set problem is deterministically solvable in O(c k ·m) time, where m denotes the number of graph edges, k...

Error compensation in leaf root problems (2004)

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier

Abstract. The k-Leaf Root problem is a particular case of graph power problems. Here, we study “error correction ” versions of k-Leaf Root—that is, for instance, adding or deleting at most l...

Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems (2004)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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.

A Structural View on Parameterizing Problems: Distance from Triviality (2004)

A structural view on parameterizing problems: distance from triviality (2004)

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...

A Structural View on Parameterizing Problems: Distance from Triviality (2004)

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...

Automated generation of search tree algorithms for hard graph modification problems (2004)

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...

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

A structural view on parameterizing problems: distance from triviality (2004)

Error compensation in leaf root problems (2004)

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...

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier

Abstract. The k-Leaf Root problem is a particular case of graph power problems. Here, we study “error correction ” versions of k-Leaf Root—that is, for instance, adding or deleting at most l...

Graph-modeled data clustering: Fixed-parameter algorithms for clique generation (2003)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

Diplomarbeit Graph Modification Problems and Automated Search Tree Generation (2003)

Falk Hüffner, Betreuer Pd, Dr. Rolf Niedermeier, Dr. Jens Gramm, Nwg Theoretische, ...

Abstract. We present a framework for the automated generation of exact search tree algorithms for NP-hard problems. The purpose of our approach is two-fold: rapid development and improved upper...

Automated Generation of Search Tree Algorithms for Graph Modification Problems (2003)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

We present a (seemingly first) 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...

Graph Modification Problems and Automated Search Tree Generation (2003)

Falk Hüffner, Betreuer Pd, Dr. Rolf Niedermeier, Dr. Jens Gramm, Nwg Theoretische, ...

We present a framework for the 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.

Graph-modeled data clustering: Fixed-parameter algorithms for clique generation (2003)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

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...

Graph-modeled data clustering: Fixed-parameter algorithms for clique generation (2003)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

Abstract. We present efficient fixed-parameter algorithms for the NPcomplete edge modification problems Cluster Editing and Cluster Deletion. Here, the goal is to make the fewest changes to the edge...

Automated generation of search tree algorithms for graph modification problems (2003)

Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

Abstract. We present a (seemingly first) 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...

Finding optimal solutions to Atomix (2001)