New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem

Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4 ^k n+n ⁴). In this paper, first we present an O(3.0446 ^k n+n ⁴) fixed-parameter algorithm and an O(2.0162 ^k n ³+n ⁵) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O ^*((1+ε) ^k ) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant.     

Chordal Deletion is Fixed-Parameter Tractable

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

Improved Parameterized Set Splitting Algorithms: A Probabilistic Approach

In this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient deterministic kernelization algorithm for the unweighted set splitting problem. We then propose a randomized algorithm for the weighted set splitting problem that is based on a new subset partition technique and has its running time bounded by O ^*(2 ^k ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O ^*(2.65 ^k ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O ^*(4 ^k ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable. A preliminary version of this paper was presented at The 13th Annual International Computing and Combinatorics Conference (COCOON 2007), Banff, Canada, July 2007, LNCS vol. 4598, pp. 537–547. This work was supported in part by the National Science Foundation under the Grant CCF-0430683.     

Fitting a Step Function to a Point Set

We consider the problem of fitting a step function to a set of points. More precisely, given an integer k and a set P of n points in the plane, our goal is to find a step function f with k steps that minimizes the maximum vertical distance between f and all the points in P. We first give an optimal Θ(nlog n) algorithm for the general case. In the special case where the points in P are given in sorted order according to their x-coordinates, we give an optimal Θ(n) time algorithm. Then, we show how to solve the weighted version of this problem in time O(nlog ⁴ n). Finally, we give an O(nh ²log n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k.     

Improved Approximation Algorithm for Convex Recoloring of Trees

A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance. The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the evolution of this set of species. In this context a convex coloring corresponds to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible, or, in other words, a tree with minimum recoloring distance. We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n ²+n(1/ε)²4^1/ε ). This result improves the previously known 3-approximation algorithm for this NP-hard problem. We also present an algorithm for computing an optimal convex recoloring whose running time is , where n ^* is the number of colors that violate convexity in the input tree, and Δ is the maximum degree of vertices in the tree. The parameterized complexity of this algorithm is O(n ²+n⋅k⋅2 ^k ).     

A New Algorithm for Finding Trees with Many Leaves

We present an algorithm that finds out-trees and out-branchings with at least k leaves in directed graphs. These problems are known as Directed Maximum Leaf Out-Tree and Directed Maximum Leaf Out-Branching, respectively, and—in the case of undirected graphs—as Maximum Leaf Spanning Tree. The run time of our algorithm is O(4 ^k nm) on directed graphs and O(poly(n)+4 ^k k ²) on undirected graphs. This improves over the previously fastest algorithms for these problems with run times of 2 ^O(klog k) poly(n) and O(poly(n)+6.75 ^k poly(k)) respectively.     

Parameterized Proof Complexity

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter (we call such a formula a parameterized contradiction). One could separate the parameterized complexity classes FPT and W[SAT] by showing that there is no fpt-bounded parameterized proof system for parameterized contradictions, i.e., that there is no proof system that admits proofs of size f(k)n ^O(1) where f is a computable function and n represents the size of the propositional formula. By way of a first step, we introduce the system of parameterized tree-like resolution and show that this system is not fpt-bounded. Indeed, we give a general result on the size of shortest tree-like resolution proofs of parameterized contradictions that uniformly encode first-order principles over a universe of size n. We establish a dichotomy theorem that splits the exponential case of Riis’s complexity gap theorem into two subcases, one that admits proofs of size f(k)n ^O(1) and one that does not. We also discuss how the set of parameterized contradictions may be embedded into the set of (ordinary) contradictions by the addition of new axioms. When embedded into general (DAG-like) resolution, we demonstrate that the pigeonhole principle has a proof of size 2 ^k n ². This contrasts with the case of tree-like resolution where the embedded pigeonhole principle falls into the “non-FPT” category of our dichotomy.     

Largest and Smallest Convex Hulls for Imprecise Points

Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(nlog n) to O(n ¹³), and prove NP-hardness for some other variants.     

Preference-based learning to rank

This paper presents an efficient preference-based ranking algorithm running in two stages. In the first stage, the algorithm learns a preference function defined over pairs, as in a standard binary classification problem. In the second stage, it makes use of that preference function to produce an accurate ranking, thereby reducing the learning problem of ranking to binary classification. This reduction is based on the familiar QuickSort and guarantees an expected pairwise misranking loss of at most twice that of the binary classifier derived in the first stage. Furthermore, in the important special case of bipartite ranking, the factor of two in loss is reduced to one. This improved bound also applies to the regret achieved by our ranking and that of the binary classifier obtained. Our algorithm is randomized, but we prove a lower bound for any deterministic reduction of ranking to binary classification showing that randomization is necessary to achieve our guarantees. This, and a recent result by Balcan et al., who show a regret bound of two for a deterministic algorithm in the bipartite case, suggest a trade-off between achieving low regret and determinism in this context. Our reduction also admits an improved running time guarantee with respect to that deterministic algorithm. In particular, the number of calls to the preference function in the reduction is improved from Ω(n ²) to O(nlog?n). In addition, when the top k ranked elements only are required (k?n), as in many applications in information extraction or search engine design, the time complexity of our algorithm can be further reduced to O(klog?k+n). Our algorithm is thus practical for realistic applications where the number of points to rank exceeds several thousand.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

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 _p 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 _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +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.     

Exact Algorithms for <Emphasis Type="Italic">L</Emphasis>(2,1)-Labeling of Graphs

The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,…,k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O ^*((k+1) ⁿ ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006 ⁿ ). Furthermore we show that dynamic programming can be used to establish an O(3.8730 ⁿ ) algorithm to compute an optimal L(2,1)-labeling.     

P2-Packing问题参数算法的改进

P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.     

Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

A sequence of exact algorithms to solve the Vertex Cover and Maximum Independent Set problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194^kk² + n) for the parameterized Vertex Cover problem on degree-3 graphs, and a simple algorithm of running time O(1.1255ⁿ) for the Maximum Independent Set problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.     

An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 ^k n ³) time algorithm for this problem, significantly improving the previous algorithm of time for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n). A preliminary version of this paper was presented at The 10th Workshop on Algorithms and Data Structures (WADS 2007). This work was supported in part by the National Science Foundation under the Grants CCR-0311590 and CCF-0430683.     

Efficient Algorithms for <Emphasis Type="Italic">k</Emphasis>-Terminal Cuts on Planar Graphs

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n ² log n logm), O(m ² n ^1.5 log² n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k ²) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n ² log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).     

Applying Modular Decomposition to Parameterized Cluster Editing Problems

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 ²) 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 ²) 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 ³) for this problem was presented by Gramm et al. (Theory Comput. Syst. 38(4), 373–392, 2005, Algorithmica 39(4), 321–347, 2004). In their solution, a problem kernel with O(k ²) vertices is built in O(n ³) time.     

Tight lower bounds for certain parameterized NP-hard problems

Based on the framework of parameterized complexity theory, we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving a general result, namely that the parameterized weighted satisfiability problem on depth-t circuits cannot be solved in time n^o(k)m^O(1), where n is the circuit input length, m is the circuit size, and k is the parameter, unless the (t − 1)-st level W[t − 1] of the W-hierarchy collapses to FPT. By refining this technique, we prove that a group of parameterized NP-hard problems, including weighted sat, hitting set, set cover, and feature set, cannot be solved in time n^o(k)m^O(1), where n is the size of the universal set from which the k elements are to be selected and m is the instance size, unless the first level W[1] of the W-hierarchy collapses to FPT. We also prove that another group of parameterized problems which includes weighted q-sat (for any fixed q 2), clique, independent set, and dominating set, cannot be solved in time n^o(k) unless all search problems in the syntactic class SNP, introduced by Papadimitriou and Yannakakis, are solvable in subexponential time. Note that all these parameterized problems have trivial algorithms of running time either n^km^O(1) or O(n^k).     

An Algorithm for Minimum Cost Arc-Connectivity Orientations

Given a 2k-edge-connected undirected graph, we consider to find a minimum cost orientation that yields a k-arc-connected directed graph. This minimum cost k-arc-connected orientation problem is a special case of the submodular flow problem. Frank (1982) devised a combinatorial algorithm that solves the problem in O(k ² n ³ m) time, where n and m are the numbers of vertices and edges, respectively. Gabow (1995) improved Frank’s algorithm to run in O(kn ² m) time by introducing a new sophisticated data structure. We describe an algorithm that runs in O(k ³ n ³+kn ² m) time without using sophisticated data structures. In addition, we present an application of the algorithm to find a shortest dijoin in O(n ² m) time, which matches the current best bound.     

Quadratic Kernelization for Convex Recoloring of Trees

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) ^k n ⁴). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k ²).     

Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines

The paper addresses the problem of multi-slot just-in-time scheduling. Unlike the existing literature on this subject, it studies a more general criterion—the minimization of the schedule makespan rather than the minimization of the number of slots used by schedule. It gives an O(nlog ² n)-time optimization algorithm for the single machine problem. For arbitrary number of m>1 identical parallel machines it presents an O(nlog n)-time optimization algorithm for the case when the processing time of each job does not exceed its due date. For the general case on m>1 machines, it proposes a polynomial time constant factor approximation algorithm.