Abstracts

Improved Exponential Time Algorithms for Vertex Cover

Authors: Jianer Chen, Iyad A. Kanj, Weijia Jia

Speaker: Jianer Chen

Abstract: In this talk, new properties for the vertex cover problem are indicated and several simple and new techniques are introduced, which lead to an improved algorithm for the problem. Our algorithm also induces improvement on previous algorithms for the independent set problem on graphs of small degree.

For a detailed hardcopy of the talk, please contact Jianer Chen at chen@cs.tamu.edu

An Exponential Algorithm for k-MAJSAT

Authors: Michael L. Littman and Toni Pitassi

Speaker: Michael L. Littman

Abstract: We have been studying satisfiability problems that are complete for complexity classes beyond NP. k-MAJSAT is the PP-complete problem of deciding whether the majority of assignments to a k-CNF formula are satisfying; it is equivalent to well-studied problems in probabilistic reasoning. We have had success adapting traditional (NP-style) satisfiability algorithms to this probabilistic setting. I will present an algorithm that runs in 1.380n for 2-MAJSAT and 1.775n algorithm for 3-MAJSAT, improving on the best published results for these problems.

References: Conference version, Journal version, Talk

Using poly-time SAT decidable and recognisable hierarchies of conjunctive normal forms for improved SAT decision and general lower bounds on resolution with oracles

Authors:

Speaker: Oliver Kullman

Abstract: I consider (cumulative) hierarchies of uniformly poly-time SAT decidable and recognisable classes H_k, k >= 0 of conjunctive normal forms, such that the union of all H_k either gives all unsatisfiable clause-sets ("U-hierarchy") or additionally also all satisfiable clause-sets ("A-hierarchy").

The associated "hardness parameter"

h(F) := the minimal k with F in Hk

is defined for all clause-sets F in case of an A-hierarchy, and only for unsatisfiable clause-sets F in case of an U-hierarchy.

Every A-hierarchy yields a SAT decision algorithm (searching through H0, H1, ...), while for an U-hierarchy additionally an upper bound u(F) on h(F) is needed, so that the algorithm can also terminate on satisfiable instances (at level u(F) + 1).

We consider three families of hierarchies and discuss the meaning of the corresponding hardness parameters, the corresponding SAT algorithms, and the (nice) relations between these hierarchies:

The first two hierarchies have been introduced in Investigating a general hierarchy of polynomially decidable classes of CNF's based on short tree-like resolution proofs, and the last in On conjunctive normal forms with small deficiency.

Slides

On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover

Authors: Rolf Niedermeier and Peter Rossmanith

Speaker: Rolf Niedermeier

Abstract: So far, parameterized complexity studies for Vertex Cover have focused on the special case of unweighted vertices. Given a graph G=(V,E) and a weight function ω: V -> R+ and k in R+, Weighted Vertex Cover (WVC for short) asks to find a subset C of vertices in V of weight at most k such that every edge of G has at least one endpoint in C. WVC and its variants studied here are NP-complete. We show that when restricting the range of ω to positive integers, then so-called Integer-WVC can be solved in time O(1.271k+kn), which is as fast as the currently best known fixed parameter algorithms for unweighted Vertex Cover. If the range of ω is restricted to positive reals ≥ 1, then we show that so-called Real-WVC can be solved in time O(1.3954k+kn). In the above general case (referred to by GENERAL-WVC), however, we can show that the problem is fixed parameter intractable unless P=NP.

Faster exact solutions for Max2Sat

Authors: Jens Gramm and Rolf Niedermeier

Speaker: Jens Gramm

Abstract: Given a boolean 2CNF formula F, the Max2Sat problem is that of finding the maximum number of clauses satisfiable simultaneously. In the corresponding decision version, we are given an additional parameter k and the question is whether we can simultaneously satisfy at least k clauses. This problem is NP-complete. We improve on known upper bounds on the worst case running time of Max2Sat, implying also new upper bounds for Maximum Cut. In particular, we give experimental results, indicating the practical relevance of our algorithms.
Keywords: NP-complete problems, exact algorithms, parameterized complexity, Max2Sat, Maximum Cut.

Maximum Independent Set Algorithms: Improved Analysis

Authors: Mike Robson

Speaker: Mike Robson

Abstract: We investigate two methods for improving the analysis of an old algorithm for finding the size of a maximum independent set of a graph, thereby slightly reducing the constant in its O(2cn) time bound. A more careful analysis of the neighbourhood of the chosen vertex in certain critical cases shows that at least one of the induced subgraphs on which the algorithm is called recursively has a property which reduces the bound known on the time for the recursive call. A tighter enumeration of the connected induced subgraphs of small order improves the economy known to be achievable by omitting duplicated computations.

Slides

Algorithms for k-SAT based on covering codes

Authors: Evgeny Dantsin and Edward Hirsch

Speaker: Edward Hirsch, Steklov Institute of Mathematics at St. Petersburg

Abstract: We show that for any k and ε, satisfiability of propositional formulas in k-CNF can be checked by a deterministic algorithm running in time poly(n) (2k/(k+1) + ε)n, where n is the number of variables in the input formula. This is the best known worst-case upper bound for deterministic k-SAT algorithms. Our algorithm can be viewed as a derandomized version of Schoning's recent algorithm (FOCS'99) whose bound poly(n) (2(k-1)/k)n is the best known bound for probabilistic 3-SAT algorithms. The key point of our derandomization is the use of covering codes. Like Schoning's algorithm, our algorithm is quite simple. Is is also possible to obtain slightly improved bounds by using a more thorough (but a more intricate) version of the algorithm. For example, for 3-SAT it is possible to achieve the bound poly(n) 1.490n.

Satisfiability Testing: Theory and Practice

Authors: Bart Selman

Speaker: Bart Selman

Abstract: Current practical Boolean satisfiability procedures can handle formulas with up to 10,000 variables and over 106 clauses from a broad range of domains. I will survey the recent progress in the development of fast satisfiability procedures. I will also discuss a series of application areas and open problems and challenges, both practical and theoretical.

An Exact Algorithm for 3-Coloring

Authors: Richard Beigel and David Eppstein

Speaker: David Eppstein

Abstract: We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS [R. Floyd & R. Beigel, The Language of Machines]. 3-SAT is equivalent to (2,3)-SSS while the other problems above are special cases of (3,2)-SSS; there is also a natural duality transformation from (a,b)-SSS to (b,a)-SSS. We give a fast algorithm for (3,2)-SSS and use it to improve the time bounds for solving the other problems listed above.

PaperSlides

Robust Algorithms for the Stable Set Problem

Authors: Vadim Lozin and Michael Gerber

Speaker: Vadim Lozin

Abstract: We describe several efficient algorithms which, given a graph G, either solve the stable set problem for G or find in it special forbidden configurations.

The complexity of k-SAT

Authors: Russell Impagliazzo and Ramamohan Paturi

Speaker: Ramamohan Paturi

Abstract: The problem of k-SAT is to determine if the given k-CNF has a satisfying solution. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k ≥ 3. Define sk (for k ≥ 3) to be the infimum of {δ : there exists an O(2δ n) algorithm for solving k-SAT} Define ETH (Exponential-Time Hypothesis) for k-SAT as follows: for k ≥ 3, sk > 0. In other words, for k ≥ 3, k-SAT does not have a subexponential-time algorithm. In this paper, we show that sk is an increasing sequence assuming ETH for k-SAT. Let s∞ be the limit of sk. We will in fact show that sk ≤ (1-d/(ek))s∞ for some constant d > 0.

Finding the closest lattice vector when it's unusually close

Authors: Philip Klein

Speaker: Philip Klein

Abstract: Lattices arise in algebraic computation, in integer programming, and in cryptography. The lattice generated by a set S of rational vectors is the set of linear integer combinations of those vectors. If the vectors of S are linearly independent, S is called a basis for the lattice.

One fundamental computational problem concerning lattices is the closest lattice vector problem: given the basis of a lattice, and given a vector x not in the lattice, find the vector in the lattice that is closest to x.

This problem is NP-hard. We give an algorithm that solves the problem; however, the time required by the algorithm depends on the distance between x and the lattice, and on the quality of the basis. The algorithm is an application of a modification of randomized rounding.

Applying Structions to the Independent Set Problem

Authors: Richard Beigel

Speaker: Richard Beigel

A struction reduces the stability number (maximum independent set size) in a graph by exactly one. We propose the use of structions in designing algorithms for the maximum independent set problem.

PaperSlides