Constant ratio fixed-parameter approximation of the edge multicut problem

The input of the Edge Multicut problem consists of an undirected graph G and pairs of terminals {s₁,t₁},…,{sm,tm}; the task is to remove a minimum set of edges such that si and ti are disconnected for every 1?i?m. The parameterized complexity of the problem, parameterized by the maximum number k of edges that are allowed to be removed, is currently open. The main result of the paper is a parameterized 2-approximation algorithm: in time f(k)⋅nO(1), we can either find a solution of size 2k or correctly conclude that there is no solution of size k.The proposed algorithm is based on a transformation of the Edge Multicut problem into a variant of the parameterized Max-2SAT problem, where the parameter is related to the number of clauses that are not satisfied. It follows from previous results that the latter problem can be 2-approximated in a fixed-parameter time; on the other hand, we show here that it is W[1]-hard. Thus the additional contribution of the present paper is introducing the first natural W[1]-hard problem that is constant-ratio fixed-parameter approximable.     

Rotation distance is fixed-parameter tractable

Rotation distance between trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In the case of ordered rooted trees, we show that the rotation distance between two ordered trees is fixed-parameter tractable, in the parameter, k, the rotation distance. The proof relies on the kernelization of the initial trees to trees with size bounded by 5k.     

A fixed-parameter tractability result for multicommodity demand flow in trees

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 problem has been intensively studied for trees as well as for general graphs mainly from the viewpoint of polynomial-time approximation algorithms. By way of contrast, we provide an exact dynamic programming algorithm for this problem that works well whenever some natural problem parameter is small, a reasonable assumption in several applications. More specifically, we prove fixed-parameter tractability with respect to the maximum number of the input flows at any tree node.     

Two fixed-parameter algorithms for Vertex Covering by Paths on Trees

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 problem is NP-hard and has recently been solved by an exact algorithm running in O(C⁴⋅²|V|) time, where C denotes the maximum number of paths covering a tree vertex. We improve this running time to O(C²⋅C⋅|V|). On the route to this, we introduce the problem Tree-like Weighted Hitting Set which might be of independent interest. In addition, for the unweighted case of Vertex Covering by Paths on Trees, we present an exact algorithm using a search tree of size O(k²⋅k!), where k denotes the number of chosen covering paths. Finally, we briefly discuss the existence of a size-O(k²) problem kernel.     

A fixed-parameter tractable algorithm for matrix domination

Matrix domination is the NP-complete problem of determining whether a given {0,1} matrix contains a set of k non-zero entries that are in the same row or same column as all other non-zero entries. Using a kernelization and search tree approach, we show the problem to be fixed-parameter tractable with running time .     

On the fixed-parameter tractability of parameterized model-checking problems

In this note, we show, through the use of examples, how generic results for proving fixed-parameter tractability which apply to restricted classes of structures can sometimes be more widely applied.     

Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

Recognition of minimal unsatisfiable CNF formulas (unsatisfiable CNF formulas which become satisfiable if any clause is removed) is a classical D^P-complete problem. It was shown recently that minimal unsatisfiable formulas with n variables and n+k clauses can be recognized in time . We improve this result and present an algorithm with time complexity ; hence the problem turns out to be fixed-parameter tractable (FTP) in the sense of Downey and Fellows (Parameterized Complexity, 1999).Our algorithm gives rise to a fixed-parameter tractable parameterization of the satisfiability problem: If for a given set of clauses F, the number of clauses in each of its subsets exceeds the number of variables occurring in the subset at most by k, then we can decide in time whether F is satisfiable; k is called the maximum deficiency of F and can be efficiently computed by means of graph matching algorithms. Known parameters for fixed-parameter tractable satisfiability decision are tree-width or related to tree-width. Tree-width and maximum deficiency are incomparable in the sense that we can find formulas with constant maximum deficiency and arbitrarily high tree-width, and formulas where the converse prevails.     

Improving exact algorithms for MAX-2-SAT

We study three new techniques that will speed up the branch-and-bound algorithm for the MAX-2-SAT problem: The first technique is a group of new lower bound functions for the algorithm and we show that these functions are admissible and consistently better than other known lower bound functions. The other two techniques are based on the strongly connected components of the implication graph of a 2CNF formula: One uses the graph to simplify the formula and the other uses the graph to design a new variable ordering. The experiments show that the simplification can reduce the size of the input substantially no matter what is the clause-to-variable ratio and that the new variable ordering performs much better when the clause-to-variable ratio is less than 2. A direct outcome of this research is a high-performance implementation of an exact algorithm for MAX-2-SAT which outperforms any implementation we know about in the same category. We also show that our implementation is a feasible and effective tool to solve large instances of the Max-Cut problem in graph theory.Preliminary results of this paper appeared in [20,21]. This research was supported in part by NSF under grant CCR-0098093.     

On-line 2-satisfiability

We deal with the followingon-line 2-satisfiability problemP(m, n): starting fromC(0)=true, consider a sequence ofm Boolean formulasC(k) (inn variables and in conjunctive normal form), each of them being the intersection of the previous one with a single clause which is the union of two literals. Solve the sequence of 2-satisfiability problemsC(k)=true,k=1,...,m. It is well known that a 2-satisfiability problem involvingm clauses can be solved inO(m) time. Thus, by a naive approach one can solveP(m, n) in overallO(m ²) time. We present an algorithm with overallO(nm) time complexity, which for every formula not only checks its satisfiability, but also actually computes a solution (if any), and moreover, detects all forced and all identical variables. Our algorithm makes use of an efficient on-line transitive closure procedure by Italiano. We discuss two applications to the design of integrated electronic circuits and to edge classification in automated perception.To the memory of Bob Jeroslow     

A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart

Abstract. A simple probabilistic algorithm for solving the NP-complete problem k -SAT is reconsidered. This algorithm follows a well-known local-search paradigm: randomly guess an initial assignment and then, guided by those clauses that are not satisfied, by successively choosing a random literal from such a clause and changing the corresponding truth value, try to find a satisfying assignment. Papadimitriou [11] introduced this random approach and applied it to the case of 2-SAT, obtaining an expected O(n ² ) time bound. The novelty here is to restart the algorithm after 3n unsuccessful steps of local search. The analysis shows that for any satisfiable k -CNF formula with n variables the expected number of repetitions until a satisfying assignment is found this way is (2⋅ (k-1)/ k) ⁿ . Thus, for 3-SAT the algorithm presented here has a complexity which is within a polynomial factor of (\frac 4 3 ) ⁿ . This is the fastest and also the simplest among those algorithms known up to date for 3-SAT achieving an o(2 ⁿ ) time bound. Also, the analysis is quite simple compared with other such algorithms considered before.     

Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(ck⋅m) time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in O(dk⋅m) time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime O(k²⋅m²) for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite.     

On Semidefinite Programming Relaxations of (2+p)-SAT

Recently, de Klerk, van Maaren and Warners [10] investigated a relaxation of 3-SAT via semidefinite programming. Thus a 3-SAT formula is relaxed to a semidefinite feasibility problem. If the feasibility problem is infeasible then a certificate of unsatisfiability of the formula is obtained. The authors proved that this approach is exact for several polynomially solvable classes of logical formulae, including 2-SAT, pigeonhole formulae and mutilated chessboard formulae. In this paper we further explore this approach, and investigate the strength of the relaxation on (2+p)-SAT formulae, i.e., formulae with a fraction p of 3-clauses and a fraction (1–p) of 2-clauses. In the first instance, we provide an empirical computational evaluation of our approach. Secondly, we establish approximation guarantees of randomized and deterministic rounding schemes when the semidefinite feasibility problem is feasible, and also present computational results for the rounding schemes. In particular, we do a numerical and theoretical comparison of this relaxation and the stronger relaxation by Karloff and Zwick [15].     

Adding cardinality constraints to integer programs with applications to maximum satisfiability

Max-SAT-CC is the following optimization problem: Given a formula in CNF and a bound k, find an assignment with at most k variables being set to true that maximizes the number of satisfied clauses among all such assignments. If each clause is restricted to have at most ? literals, we obtain the problem Max-?SAT-CC. Sviridenko [Algorithmica 30 (3) (2001) 398-405] designed a (1−e⁻¹)-approximation algorithm for Max-SAT-CC. This result is tight unless P=NP [U. Feige, J. ACM 45 (4) (1998) 634-652]. Sviridenko asked if it is possible to achieve a better approximation ratio in the case of Max-?SAT-CC. We answer this question in the affirmative by presenting a randomized approximation algorithm whose approximation ratio is . To do this, we develop a general technique for adding a cardinality constraint to certain integer programs. Our algorithm can be derandomized using pairwise independent random variables with small probability space.     

Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances

An analysis of the average-case complexity of solving random 3-Satisfiability (SAT) instances with backtrack algorithms is presented. We first interpret previous rigorous works in a unifying framework based on the statistical physics notions of dynamical trajectories, phase diagram and growth process. It is argued that, under the action of the Davis–Putnam–Loveland–Logemann (DPLL) algorithm, 3-SAT instances are turned into 2+p-SAT instances whose characteristic parameters (ratio of clauses per variable, fraction p of 3-clauses) can be followed during the operation, and define resolution trajectories. Depending on the location of trajectories in the phase diagram of the 2+p-SAT model, easy (polynomial) or hard (exponential) resolutions are generated. Three regimes are identified, depending on the ratio of the 3-SAT instance to be solved. Lower satisfiable (sat) phase: for small ratios, DPLL almost surely finds a solution in a time growing linearly with the number N of variables. Upper sat phase: for intermediate ratios, instances are almost surely satisfiable but finding a solution requires exponential time (2^Nω with ω>0) with high probability. Unsat phase: for large ratios, there is almost always no solution and proofs of refutation are exponential. An analysis of the growth of the search tree in both upper sat and unsat regimes is presented, and allows us to estimate ω as a function of . This analysis is based on an exact relationship between the average size of the search tree and the powers of the evolution operator encoding the elementary steps of the search heuristic.     

Exploiting multivalued knowledge in variable selection heuristics for SAT solvers

We show that we can design and implement extremely efficient variable selection heuristics for SAT solvers by identifying, in Boolean clause databases, sets of Boolean variables that model the same multivalued variable and then exploiting that structural information. In particular, we define novel variable selection heuristics for two of the most competitive existing SAT solvers: Chaff, a solver based on look-back techniques, and Satz, a solver based on look-ahead techniques. Our heuristics give priority to Boolean variables that belong to sets of variables that model multivalued variables with minimum domain size in a given state of the search process. The empirical investigation conducted to evaluate the new heuristics provides experimental evidence that identifying multivalued knowledge in Boolean clause databases and using variable selection heuristics that exploit that knowledge leads to large performance improvements.      

参数为k的几乎树中的染色多路割

染色多路割问题源于对等网络中的数据分片,是传统多路割问题的推广。给定颜色相关边赋权图G和G上若干特异顶点的局部染色,将该局部染色扩展到所有顶点上,使得两端点染不同颜色的边的权和最小。对于参数为k的几乎树,给出了多项式时间精确算法。也就是说,染色多路割问题是固定参数可解的,其中的参数k是使得G中任意双连通分支C成为树所要拿掉的最大边数。     

Going weighted: Parameterized algorithms for cluster editing

The goal of the Cluster Editing problem is to make the fewest changes to the edge set of an input graph such that the resulting graph is a disjoint union of cliques. This problem is NP-complete but recently, several parameterized algorithms have been proposed. In this paper, we present a number of surprisingly simple search tree algorithms for Weighted Cluster Editing assuming that edge insertion and deletion costs are positive integers. We show that the smallest search tree has size O(1.82^k) for edit cost k, resulting in the currently fastest parameterized algorithm, both for this problem and its unweighted counterpart. We have implemented and compared our algorithms, and achieved promising results.¹     

An improved kernelization algorithm for r-Set Packing

We present a reduction procedure that takes an arbitrary instance of the r-Set Packing problem and produces an equivalent instance whose number of elements is in O(kr−1), where k is the input parameter. Such parameterized reductions are known as kernelization algorithms, and a reduced instance is called a problem kernel. Our result improves on previously known kernelizations by a factor of k. In particular, the number of elements in a 3-Set Packing kernel is improved from a cubic function of the parameter to a quadratic one.