Exponential-time approximation of weighted set cover

The Set Cover problem belongs to a group of hard problems which are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. In recent years, many researchers design exact exponential-time algorithms for problems of that kind. The goal is getting the time complexity still of order O(cn), but with the constant c as small as possible. In this work we extend this line of research and we investigate whether the constant c can be made even smaller when one allows constant factor approximation.In fact, we describe a kind of approximation schemes—trade-offs between approximation factor and the time complexity. We use general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate r, one can transform any O^∗(cn)-time¹ algorithm for Set Cover into a (1+lnr)-approximation algorithm running in time O^∗(cn/r). We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems.     

Set multi-covering via inclusion–exclusion

Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion–exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O^*((2t)ⁿ) time and O^*((t+1)ⁿ) space where t is the maximum value in the coverage requirement set (The O^*(f(n)) notation omits a polylog(f(n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion–exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)].     

Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2 ^m l ^O(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2 ⁿ n ^O(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732 ⁿ ) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.     

Improved fixed parameter tractable algorithms for two “edge” problems: MAXCUT and MAXDAG

We give improved parameterized algorithms for two “edge” problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems. More precisely our results include:

(i)

a kernel with at most αk vertices and βk edges for MAXCUT. Here 0<α?1 and 1<β?2. Values of α and β depends on the number of vertices and the edges in the graph;

(ii)

a kernel with at most 4k/3 vertices and 2k edges for MAXDAG;

(iii)

an O^∗(k^1.2418) parameterized algorithm for MAXCUT in undirected graphs. This improves the O^∗(k^1.4143)¹ algorithm presented in [E. Prieto, The method of extremal structure on the k-maximum cut problem, in: The Proceedings of Computing: The Australasian Theory Symposium (CATS), 2005, pp. 119-126];

(iv)

an O^∗(n²) algorithm for optimization version of MAXDAG in directed graphs. This is the first such algorithm to the best of our knowledge;

(v)

an O^∗(k²) parameterized algorithm for MAXDAG in directed graphs. This improves the previous best of O^∗(k⁴) presented in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458];

(vi)

an O^∗(k¹⁶) parameterized algorithm to determine whether an oriented graph having m arcs has an acyclic subgraph with at least m/2+k arcs. This improves the O^∗(k²) algorithm given in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458].

In addition, we show that if a directed graph has minimum out degree at least f(n) (some function of n) then Directed Feedback Arc Set problem is fixed parameter tractable. The parameterized complexity of Directed Feedback Arc Set is a well-known open problem.     

On the existence of subexponential parameterized algorithms

The existence of subexponential-time parameterized algorithms is examined for various parameterized problems solvable in time O(2^O(k)p(n)). It is shown that for each t?1, there are parameterized problems in FPT for which the existence of O(2^o(k)p(n))-time parameterized algorithms implies the collapse of W[t] to FPT. Evidence is demonstrated that Max-SNP-hard optimization problems do not admit subexponential-time parameterized algorithms. In particular, it is shown that each Max-SNP-complete problem is solvable in time O(2^o(k)p(n)) if and only if 3-SAT∈DTIME(2^o(n)). These results are also applied to show evidence for the non-existence of -time parameterized algorithms for a number of other important problems such as Dominating Set, Vertex Cover, and Independent Set on planar graph instances.     

Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates

In this paper, we consider a single-machine scheduling problem with release dates. The aim is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose two new lower bounds that can be, respectively, computed in O(n²) and in O(nlogn) time where n is the number of jobs. We prove a sufficient and necessary condition for local optimality, which can also be considered as a priority rule. We present an efficient heuristic using such a condition. We also propose some dominance properties. A branch-and-bound algorithm incorporating the heuristic, the lower bounds and the dominance properties is proposed and tested on a large set of instances.     

加权3-Set Packing 的改进算法

Packing 问题构成了一类重要的NP 难问题.对于加权3-Set Packing 问题,把问题转化成加权3-Set Packing Augmentation 问题进行求解,即主要讨论如何从一个已知的最大加权k-packing 求得一个权值最大的(k+1)-packing. 通过对问题结构的分析,结合Color-Coding 技术,首先给出了一种时间复杂度为O^*(10.6^3k)的参数算法,极大地改进了目前文献中的最好结果O^*(12.8^3k).通过对(k+1)-packing 结构的进一步分析,利用集合划分技术将上述结果降到O^*(7.56^3k).     

Contracting Graphs to Paths and Trees

Vertex deletion and edge deletion problems play a central role in parameterized complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. The study of analogous edge contraction problems has so far been left largely unexplored from a parameterized perspective. We consider two basic problems of this type: Tree Contraction and Path Contraction. These two problems take as input an undirected graph G on n vertices and an integer k, and the task is to determine whether we can obtain a tree or a path, respectively, by a sequence of at most k edge contractions in G. For Tree Contraction, we present a randomized 4 ^k ? n ^O(1) time polynomial-space algorithm, as well as a deterministic 4.98 ^k ? n ^O(1) time algorithm, based on a variant of the color coding technique of Alon, Yuster and Zwick. We also present a deterministic 2 ^k+o(k)+n ^O(1) time algorithm for Path Contraction. Furthermore, we show that Path Contraction has a kernel with at most 5k+3 vertices, while Tree Contraction does not have a polynomial kernel unless NP ? coNP/poly. We find the latter result surprising because of the connection between Tree Contraction and Feedback Vertex Set, which is known to have a kernel with 4k ² vertices.     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

Delay Optimization in Quorum Consensus

The management of replicated data in distributed database systems is a classic problem with great practical importance. Quorum consensus is one of the popular methods, combined with eager replication, for managing replicated data. In this paper we investigate the problems of delay-optimal quorum consensus. Firstly, we show that the problem of minimizing the total delay (or mean delay) restricted to a ring can be solved in a constant time in contrast to the existing approximation results. Secondly, we show that the problem of minimizing the total delay (or mean delay) is NP-hard. Thirdly, we present an approximate algorithm with an approximate ratio 2; and the approximate algorithm can guarantee the exact solutions for some specific network topology, such as trees and meshes. Finally, we present an improvement on the existing algorithm to solve the problem of minimizing the maximal delay; this reduces the time complexity from O(n ³ log n) to O(n ³) where n is the number of nodes.     

Delay Optimization in Quorum Consensus

The management of replicated data in distributed database systems is a classic problem with great practical importance. Quorum consensus is one of the popular methods, combined with eager replication, for managing replicated data. In this paper we investigate the problems of delay-optimal quorum consensus. Firstly, we show that the problem of minimizing the total delay (or mean delay) restricted to a ring can be solved in a constant time in contrast to the existing approximation results. Secondly, we show that the problem of minimizing the total delay (or mean delay) is NP-hard. Thirdly, we present an approximate algorithm with an approximate ratio 2; and the approximate algorithm can guarantee the exact solutions for some specific network topology, such as trees and meshes. Finally, we present an improvement on the existing algorithm to solve the problem of minimizing the maximal delay; this reduces the time complexity from O(n ³ log n) to O(n ³) where n is the number of nodes.     

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.     

Scheduling a Single Server in a Two-machine Flow Shop

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n ³) time when all job processing times on the first machine are equal, and it is solved in O(n ⁴) time when all processing times on the second machine are equal. Received November 20, 2001; revised October 18, 2002 Published online: January 16, 2003     

Scheduling two jobs with fixed and nonfixed routes

The shop-scheduling problem with two jobs andm machines is considered under the condition that the machine order is fixed in advance for the first job and nonfixed for the second job. The problems of makespan and mean flow time minimization are proved to be NP-hard if operation preemption is forbidden. In the case of preemption allowance for any given regular criterion theO(n _*) algorithm is proposed. Here,n _* is the maximum number of operations per job.     

Kernels for feedback arc set in tournaments

A tournament T=(V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T^′ on O(k) vertices. In fact, given any fixed ?>0, the kernelized instance has at most (2+?)k vertices. Our result improves the previous known bound of O(k²) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST.     

Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems

Pseudo-kernelization is introduced in this paper as a new strategy for improving fixed-parameter algorithms. This new technique works for bounded search tree algorithms by identifying favorable branching conditions whose absence could be used to reduce the size of corresponding problem instances. Pseudo-kernelization applies well to hitting set problems. It can be used either to improve the search tree size of a 3-Hitting-Set algorithm from O^*(2.179^k) to O^*(2.05^k), or to improve the kernel size from k³ to 27k. In this paper the parameterized 3-Hitting-Set and Face Cover problems are used as typical examples.     

Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover

We present a new method of solving graph problems related to Vertex Cover by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the Vertex Cover problem. In the case of Connected Vertex Cover, we take the upper bound from O ^*(6 ^k ) to O ^*(2.7606 ^k ) without large hidden factors. For Tree Cover, we show a complexity of O ^*(3.2361 ^k ), improving over the previous bound of O ^*((2k) ^k ). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated. Supported by the DFG under grant RO 927/6-1 (TAPI).     

Approximate algorithms for the knapsack problem on parallel computers

Computing an optimal solution to the knapsack problem is known to be NP-hard. Consequently, fast parallel algorithms for finding such a solution without using an exponential number of processors appear unlikely. An attractive alternative is to compute an approximate solution to this problem rapidly using a polynomial number of processors. In this paper, we present an efficient parallel algorithm for finding approximate solutions to the 0–1 knapsack problem. Our algorithm takes an , 0 < < 1, as a parameter and computes a solution such that the ratio of its deviation from the optimal solution is at most a fraction of the optimal solution. For a problem instance having n items, this computation uses O(n^5/2/^3/2) processors and requires O(log³n + log²nlog(1/)) time. The upper bound on the processor requirement of our algorithm is established by reducing it to a problem on weighted bipartite graphs. This processor complexity is a significant improvement over that of other known parallel algorithms for this problem.     

Boolean-width of graphs

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods-Boolean sums of neighborhoods-across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n²k2^2k) and Minimum Weight Dominating Set in time O(n²+nk2^3k). With an additional n² factor in the runtime, we can also count all independent sets and dominating sets of each cardinality.Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n²) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n).     

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.