Two Fixed-Parameter Algorithms for Vertex Covering by Paths on Trees 1 (2009)
Jiong Guo, Rolf Niedermeier, Johannes Uhlmann
Vertex Covering by Paths on Trees with applications in machine translation is the task to cover all vertices of a tree T = (V,E) by choosing a minimum-weight subset of given paths in the tree. The...
Improved Algorithms for Bicluster Editing (2009)
Jiong Guo, Falk Hüffner, Christian Komusiewicz, Yong Zhang
Abstract. The NP-hard Bicluster Editing is to add or remove at most k edges to make a bipartite graph G = (V, E) a vertex-disjoint union of complete bipartite subgraphs. It has applications in the...
Fixed-Parameter Algorithms for Kemeny Scores (2009)
Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Frances A. Rosamond
Abstract. The Kemeny Score problem 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...
Iterative compression for exactly solving np-hard minimization problems (2009)
Jiong Guo, Hannes Moser, Rolf Niedermeier
Abstract. We survey the conceptual framework and several applications of the iterative compression technique introduced in 2004 by Reed, Smith, and Vetta. This technique has proven very useful for...
Computing Kemeny Rankings, Parameterized by the Average KT-Distance (2009)
Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Frances A. Rosamond
The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Unfortunately, the problem is NP-hard. Extending our previous work [AAIM 2008], we show that the...
Michael Dom, Jiong Guo, Rolf Niedermeier, Sebastian Wernicke
Set Cover problems are of core importance in many applications. In recent research, the “red-blue variants ” where blue elements all need to be covered whereas red elements add further...
A Generalization of Nemhauser and Trotter's Local Optimization Theorem (2009)
Fellows, Michael R., Guo, Jiong, Moser, Hannes, Niedermeier, Rolf
The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We present a framework that...
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...
A Generalization of Nemhauser and Trotter's Local Optimization Theorem (2009)
Fellows, Michael R., Guo, Jiong, Moser, Hannes, Niedermeier, Rolf
The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We present a framework that...
A Generalization of Nemhauser and Trotter's Local Optimization Theorem (2009)
Fellows, Michael R., Guo, Jiong, Moser, Hannes, Niedermeier, Rolf
The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We present a framework that...
A Generalization of Nemhauser and Trotter's Local Optimization Theorem (2009)
Fellows, Michael R., Guo, Jiong, Moser, Hannes, Niedermeier, Rolf
The Nemhauser-Trotter local optimization theorem applies to the NP-hard textsc{Vertex Cover} problem and has applications in approximation as well as parameterized algorithmics. We present a...
Red-Blue Covering Problems and the Consecutive Ones Property 1 (2008)
Michael Dom, Jiong Guo, Rolf Niedermeier, Sebastian Wernicke
Set Cover problems are of core importance in many applications. In recent research, the “red-blue variants ” where blue elements all need to be covered whereas red elements add further...
Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs (2008)
Abstract. In an edge deletion problem one is asked to delete at most k edges from a given graph such that the resulting graph satisfies a certain property. In this work, we study four NP-complete...
A Fixed-Parameter Tractability Result for Multicommodity Demand Flow in Trees 1 Abstract (2008)
We study an NP-hard (and MaxSNP-hard) problem in trees—Multicommodity Demand Flow—dealing with demand flows between pairs of nodes and trying to maximize the value of the routed flows. This...
Probe Matrix Problems: Totally Balanced Matrices (2008)
David B. Ch, Jiong Guo, Ton Kloks, Rolf Niedermeier
Abstract. Let M be a class of 0/1-matrices. A 0/1/⋆-matrix A where the ⋆s induce a submatrix is a probe matrix of M if the ⋆s in A can be replaced by 0s and 1s such that A becomes a member of...
Kernelization and Complexity Results for Connectivity Augmentation Problems (2008)
Abstract. Connectivity augmentation problems ask for adding a set of at most k edges whose insertion makes a given graph satisfy a specified connectivity property, such as bridge-connectivity or...
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...
Jiong Guo, Rolf Niedermeier, Sebastian Wernicke
Abstract. We provide first-time fixed-parameter tractability results for
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...
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,...
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...
Open Problems in Parameterized and Exact Computation — (2008)
Hans L. Bodlaender, Erik D. Demaine, Michael R. Fellows, Jiong Guo, Danny Hermelin, Daniel Lokshtanov, ...
www.cs.uu.nl
A more effective linear kernelization for cluster editing (2007)
Abstract. In the NP-hard Cluster Editing problem, we have as input an undirected graph G and an integer k ≥ 0. The question is whether we can transform G, by inserting and deleting at most k edges,...
Approximability and parameterized complexity of consecutive ones submatrix problems (2007)
Michael Dom, Jiong Guo, Rolf Niedermeier
Abstract. We develop a refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This novel characterization finds applications in new...
Linear problem kernels for NP-hard problems on planar graphs (2007)
Abstract. We develop a generic framework for deriving linear-size problem kernels for NP-hard problems on planar graphs. We demonstrate the usefulness of our framework in several concrete case...
Parameterized computational complexity of Dodgson and Young elections (2007)
Nadja Betzler, Jiong Guo, Rolf Niedermeier
Abstract. We show that, other than for standard complexity theory with known NP-completeness results, the computational complexity of the Dodgson and Young election systems is completely different...
Algorithm design techniques for parameterized graph modification problems (2006)
Diese Arbeit beschaeftigt sich mit dem Entwurf parametrisierter Algorithmen fuer Graphmodifikationsprobleme wie Feedback Vertex Set, Multicut in Trees, Cluster Editing und Closest 3-Leaf Powers....
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...
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...
THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS ∗ (2006)
Sebastian Wernicke, Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
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...
Fixed-parameter tractability results for feedback set problems in tournaments (2006)
Michael Dom, Jiong Guo, 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...
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...
Parameterized intractability of distinguishing substring selection (2006)
Jens Gramm, Jiong Guo, Rolf Niedermeier
A central question in computational biology is the design of genetic markers to distinguish between two given sets of (DNA) sequences. This question is formalized as the NP-complete Distinguishing...
Minimum membership set covering and the consecutive ones property (2006)
Michael Dom, Jiong Guo, Rolf Niedermeier, Sebastian Wernicke
Abstract. The Minimum Membership Set Cover problem has recently been introduced and studied in the context of interference reduction in cellular networks. It has been proven to be notoriously hard in...
Vertex Cover, Capacitated Vertex Cover, and Maximum (2006)
Jiong Guo, Rolf Niedermeier, Sebastian Wernicke
Important variants of the Vertex Cover problem (among others, Connected
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...
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...
Bounded degree Closest k-Tree Power is NP-complete (2005)
Michael Dom, Jiong Guo, Rolf Niedermeier
Abstract. An undirected graph G = (V, E) is the k-power of an undirected tree T = (V, E ′ ) if (u, v) ∈ E iff u and v are connected by a path of length at most k in T. The tree T is called the...
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 algorithms and complexity results for power domination (2005)
Jiong Guo, Rolf Niedermeier, Daniel Raible
Abstract. The Power Dominating Set problem is a variant of the classical domination problem in graphs: Given an undirected graph G = (V, E), find a minimum P ⊆ V such that all vertices in V are...
Improved algorithms and complexity results for power domination (2005)
Jiong Guo, Rolf Niedermeier, Daniel Raible
The NP-complete Power Dominating Set problem is an “electric power networks variant ” of the classical domination problem in graphs: Given an undirected graph G = (V, E), find a minimum-size set...
Parameterized complexity of generalized vertex cover problems (2005)
Jiong Guo, Rolf Niedermeier, Sebastian Wernicke
Abstract. Important generalizations of the Vertex Cover problem
Improved algorithms and complexity results for power domination (2005)
Jiong Guo, Rolf Niedermeier, Daniel Raible
Abstract. The Power Dominating Set problem is a variant of the classical domination problem in graphs: Given an undirected graph G = (V, E), find a minimum P ⊆ V such that all vertices in V are...
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...
Fixed-parameter tractability and data reduction for Multicut in Trees (2005)
We study an NP-complete (and MaxSNP-hard) communication problem on tree networks, the so-called Multicut in Trees: given an undirected tree and some pairs of nodes of the tree, find out whether there...
Computing the similarity of two sequences with nested arc annotations (2004)
Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
We present exact algorithms for the NP-complete Longest Common Subsequence problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two sequences...
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)
Jiong Guo, Falk Hüffner, Rolf Niedermeier
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...
Avoiding Forbidden Submatrices by Row Deletions (2004)
Sebastian Wernicke, Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
We initiate a systematic study of the Row Deletion(B) problem on matrices: For a fixed "forbidden submatrix" B, the question is, given an input matrix A (both A and B have entries chosen...
Exact algorithms and applications for Tree-like Weighted Set Cover (2004)
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...
Avoiding forbidden submatrices by row deletions (2004)
Sebastian Wernicke, Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
Abstract. We initiate a systematic study of the Row Deletion(B) problem on matrices: For a fixed “forbidden submatrix ” B, the question is, given an input matrix A (both A and B have entries...
Computing the similarity of two sequences with nested arc annotations (2004)
Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
We present exact algorithms for the NP-complete Longest Common Subsequence problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two sequences...
A structural view on parameterizing problems: distance from triviality (2004)
Jiong Guo, Falk Hüffner, Rolf Niedermeier
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...
A Structural View on Parameterizing Problems: Distance from Triviality (2004)
Jiong Guo, Falk Hüffner, Rolf Niedermeier
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)
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)
Jiong Guo, Falk Hüffner, Rolf Niedermeier
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...
Computing the similarity of two sequences with nested arc annotations (2004)
Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
We present exact algorithms for the NP-complete Longest Common Subsequence problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two sequences...
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...
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...
On exact and approximation algorithms for Distinguishing Substring Selection (2003)
Jens Gramm, Jiong Guo, Rolf Niedermeier
Abstract. The NP-complete Distinguishing Substring Selection problem (DSSS for short) asks, given a set of "good " strings and a set of "bad" strings, for a...
Graph-modeled data clustering: Fixed-parameter algorithms for clique generation (2003)
Jens Gramm, Jiong Guo, Rolf Niedermeier
Abstract. We present e#cient 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
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-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...
On exact and approximation algorithms for Distinguishing Substring Selection (2003)
Jens Gramm, Jiong Guo, Rolf Niedermeier
Abstract. The NP-complete Distinguishing Substring Selection problem (DSSS for short) asks, given a set of “good ” strings and a set of “bad” strings, for a solution string which is, with...
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...
Pattern matching for arc-annotated sequences (2002)
Jens Gramm, Jiong Guo, Rolf Niedermeier
Abstract. A study of pattern matching for arc-annotated sequences is started. An O(nm) time algorithm is given to determine whether a length m sequence with nested arc annotations is an...
Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
Abstract. We present exact algorithms for the NP-complete Longest Common Subsequence problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two...
Computing the Similarity of Two Sequences with Nested Arc Annotations (2002)
Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
We present exact algorithms for the NP-complete Longest Common Subsequence problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two sequences...
Pattern matching for arc-annotated sequences (2002)
Jens Gramm, Jiong Guo, Rolf Niedermeier
We study pattern matching for arc-annotated sequences. An O(nm) time algorithm is given for the problem to determine whether a length m sequence with nested arc annotation is an arc-preserving...
Jochen Alber, Jens Gramm, Jiong Guo, Rolf Niedermeier
Abstract. We present exact algorithms for the NP-complete Longest Common Subsequence problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two...