Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems

We obtain faster algorithms for problems such as r-dimensional matching and r-set packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). This technique lets us combine Alon, Yuster and Zwick’s color-coding technique with dynamic programming to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2 ^O(k)), an improvement over previous algorithms for some of these problems running in time O(n+k ^O(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent. Research initiated at the International Workshop on Fixed Parameter Tractability in Computational Geometry and Games, Bellairs Research Institute of McGill University, Holetown, Barbados, Feb. 7–13, 2004, organized by S. Whitesides. D.M. Thilikos supported by the EU within the 6th Framework Programme under contract 001907 (DELIS) and by the Spanish CICYT project TIC-2002-04498-C05-03 (TRACER).     

Approximation and Tidying—A Problem Kernel for?s-Plex Cluster Vertex Deletion

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

Fixed-Parameter Enumerability of Cluster Editing and Related Problems

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

Faster Combinatorial Algorithms for Determinant and Pfaffian

Computation of a determinant is a very classical problem. The related concept is a Pfaffian of a matrix defined for skew-symmetric matrices. The classical algorithm for computing the determinant is Gaussian elimination. It needs O(n ³) additions, subtractions, multiplications and divisions. The algorithms of Mahajan and Vinay compute determinant and Pfaffian in a completely non-classical and combinatorial way, by reducing these problems to summation of paths in some acyclic graphs. The attractive feature of these algorithms is that they are division-free. We present a novel algebraic view of these algorithms: a relation to a pseudo-polynomial dynamic-programming algorithm for the knapsack problem. The main phase of Mahajan-Vinay algorithm can be interpreted as a computation of an algebraic version of the knapsack problem, which is an alternative to the graph-theoretic approach used in the original algorithm. Our main results show how to implement Mahajan-Vinay algorithms without divisions, in time $\tilde{O}(n^{3.03})$ using the fast matrix multiplication algorithm.     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

Approximation Algorithms for Bounded Degree Phylogenetic Roots

The Degree- Δ Closest Phylogenetic k th Root Problem (ΔCPR _k ) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E ⊕{{u,v} : u,v are leaves of T and d _T (u,v)≤k}|, is minimized, where d _T (u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for Δ CPR ₂ for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR ₃, and a polynomial-time approximation scheme for the maximization version of Δ CPR _k for any fixed Δ and k.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

Simple and Improved Parameterized Algorithms for Multiterminal Cuts

Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min?(n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: $O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min (n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: O((min(?{2k},l)+1)^2k2^lT(n,m))O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m)) -time algorithm for Edge Multicut and O((2k) ^k+l/2 T(n,m))-time algorithm for Vertex Multicut.     

Improved Algorithms for Maximum Agreement and Compatible Supertrees

Consider a set of labels L and a set of unordered trees \(\mathcal{T}=\{\mathcal{T}^{(1)},\mathcal{T}^{(2)},\ldots ,\allowbreak \mathcal{T}^{(k)}\}\) where each tree \(\mathcal{T}^{(i)}\) is distinctly leaf-labeled by some subset of L. One fundamental problem is to find the biggest tree (denoted as supertree) to represent \(\mathcal{T}\) which minimizes the disagreements with the trees in \(\mathcal{T}\) under certain criteria. In this paper, we focus on two particular supertree problems, namely, the maximum agreement supertree problem (MASP) and the maximum compatible supertree problem (MCSP). These two problems are known to be NP-hard for k≥3. This paper gives improved algorithms for both MASP and MCSP. In particular, our results imply the first polynomial time algorithms for both MASP and MCSP when both k and the maximum degree D of the input trees are constant.     

Competitive Analysis of Scheduling Algorithms for Aggregated Links

We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the maximum flow time is minimized. We present a deterministic online algorithm with competitive ratio , and show a matching lower bound, even for randomized algorithms. The performance bound for we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions (when many jobs are released in a short amount of time), ’s performance is close to the optimum. We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is -hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal algorithm for k=1, and a 2-approximation algorithm for any k. W. Jawor and M. Chrobak supported by NSF grants OISE-0340752 and CCR-0208856. Work of C. Dürr conducted while being affiliated with the Laboratoire de Recherche en Informatique, Université Paris-Sud, 91405 Orsay. Supported by the CNRS/NSF grant 17171 and ANR Alpage.     

Linear Time Algorithms for Generalizations of the Longest Common Substring Problem

In its simplest form, the longest common substring problem is to find a longest substring common to two or multiple strings. Using (generalized) suffix trees, this problem can be solved in linear time and space. A first generalization is the k -common substring problem: Given m strings of total length n, for all k with 2≤k≤m simultaneously find a longest substring common to at least k of the strings. It is known that the k-common substring problem can also be solved in O(n) time (Hui in Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, volume 644 of Lecture Notes in Computer Science, pp. 230–243, Springer, Berlin, 1992). A further generalization is the k -common repeated substring problem: Given m strings T ⁽¹⁾,T ⁽²⁾,…,T ^(m) of total length n and m positive integers x ₁,…,x _m , for all k with 1≤k≤m simultaneously find a longest string ω for which there are at least k strings \(T^{(i_{1})},T^{(i_{2})},\ldots,T^{(i_{k})}\) (1≤i ₁<i ₂<???<i _k ≤m) such that ω occurs at least \(x_{i_{j}}\) times in \(T^{(i_{j})}\) for each j with 1≤j≤k. (For x ₁=???=x _m =1, we have the k-common substring problem.) In this paper, we present the first O(n) time algorithm for the k-common repeated substring problem. Our solution is based on a new linear time algorithm for the k-common substring problem.     

Improved Algorithms for Polynomial-Time Decay and Time-Decay with Additive Error

We consider the problem of maintaining polynomial and exponential decay aggregates of a data stream, where the weight of values seen from the stream diminishes as time elapses. These types of aggregation were discussed by Cohen and Strauss (J. Algorithms 1(59), 2006), and can be used in many applications in which the relative value of streaming data decreases since the time the data was seen. Some recent work and space efficient algorithms were developed for time-decaying aggregations, and in particular polynomial and exponential decaying aggregations. All of the work done so far has maintained multiplicative approximations for the aggregates. In this paper we present the first O(log N) space algorithm for the polynomial decay under a multiplicative approximation, matching a lower bound. In addition, we explore and develop algorithms and lower bounds for approximations allowing an additive error in addition to the multiplicative error. We show that in some cases, allowing an additive error can decrease the amount of space required, while in other cases we cannot do any better than a solution without additive error.     

On Nonmonotone Chambolle Gradient Projection Algorithms for Total Variation Image Restoration

The main aim of this paper is to accelerate the Chambolle gradient projection method for total variation image restoration. In the proposed minimization method model, we use the well known Barzilai-Borwein stepsize instead of the constant time stepsize in Chambolle’s method. Further, we adopt the adaptive nonmonotone line search scheme proposed by Dai and Fletcher to guarantee the global convergence of the proposed method. Numerical results illustrate the efficiency of this method and indicate that such a nonmonotone method is more suitable to solve some large-scale inverse problems.

High-Order Two-Dimension Cluster Competitive Activation Mechanisms Used for Performing Symbolic Logic Algorithms of Problem Solving

This paper presents a neural network approach,based on high-order twodimension temporal and dynamically clustering competitive activation mechanisms,to implement parallel searching algorithm and many other symbolic logic algorithms.This approach is superior in many respects to both the common sequential algorithms of symbolic logic and the common neural network used for optimization problems.Simulations of problem solving examples prove the effectiveness of the approach.     

The Cache Complexity of Multithreaded Cache Oblivious Algorithms

We present a technique for analyzing the number of cache misses incurred by multithreaded cache oblivious algorithms on an idealized parallel machine in which each processor has a private cache. We specialize this technique to computations executed by the Cilk work-stealing scheduler on a machine with dag-consistent shared memory. We show that a multithreaded cache oblivious matrix multiplication incurs cache misses when executed by the Cilk scheduler on a machine with P processors, each with a cache of size Z, with high probability. This bound is tighter than previously published bounds. We also present a new multithreaded cache oblivious algorithm for 1D stencil computations incurring cache misses with high probability, one for Gaussian elimination and back substitution, and one for the length computation part of the longest common subsequence problem incurring cache misses with high probability. This work was supported in part by the Defense Advanced Research Projects Agency (DARPA) under contract No. NBCH30390004.     

Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

We show that several problems that are hard for various parameterized complexity classes on general graphs, become fixed parameter tractable on graphs with no small cycles. More specifically, we give fixed parameter tractable algorithms for Dominating Set, t -Vertex Cover (where we need to cover at least t edges) and several of their variants on graphs with girth at least five. These problems are known to be W[i]-hard for some i≥1 in general graphs. We also show that the Dominating Set problem is W[2]-hard for bipartite graphs and hence for triangle free graphs. In the case of Independent Set and several of its variants, we show these problems to be fixed parameter tractable even in triangle free graphs. In contrast, we show that the Dense Subgraph problem where one is interested in finding an induced subgraph on k vertices having at least l edges, parameterized by k, is W[1]-hard even on graphs with girth at least six. Finally, we give an O(log p) ratio approximation algorithm for the Dominating Set problem for graphs with girth at least 5, where p is the size of an optimum dominating set of the graph. This improves the previous O(log n) factor approximation algorithm for the problem, where n is the number of vertices of the input graph. A preliminary version of this paper appeared in the Proceedings of 10th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 4059, pp. 304–315, 2006.     

Two Algorithms for Fast Polyhedron Ray-Tracing

ＴｗｏＡｌｇｏｒｉｔｈｍｓｆｏｒＦａｓｔＰｏｌｙｈｅｄｒｏｎＲａｙ－ＴｒａｃｉｎｇＺｈａｎｇＱｉａｎＳｈｉＪｉａｏｙｉｎｇＣａｉＨｏｎｇＣＡＤ＆ＣＧＳｔａｔｅＫｅｙＬａｂ．，ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙ，３１００２７ＦｏｓｈａｎＥｎｔｅｒｐｒ...     

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

In a finite undirected graph, an apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one of the cycle vertices. A graph is apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs, claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination of clique separators with modular decomposition. Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class; the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class.     

Algorithms for the Gauss–Manin Connection

We give an introduction to the theory of the Gauss–Manin connection of an isolated hypersurface singularity and describe an algorithm to compute the V-filtration on the Brieskorn lattice. We use an implementation in the computer algebra system Singular to prove C. Hertling’s conjecture about the variance of the spectrum for Milnor numberμ ≤  16.