We provide new non-approximability results for the restrictions of the min-VC problem to bounded-degree, sparse and dense graphs. We show that for a sufficiently large B, the recent 16/15 lower bound proved by Bellare et al. extends with negligible loss to graphs with bounded degree B. Then, we consider sparse ... more >>>

In 1978, Schaefer considered a subclass of languages in NP and proved a ``dichotomy theorem'' for this class. The subclass considered were problems expressible as ``constraint satisfaction problems'', and the ``dichotomy theorem'' showed that every language in this class is either in P, or is NP-hard. This result is in ... more >>>

The bandwidth problem is the problem of enumerating the vertices of a given graph $G$ such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications and is known to be $NP$-hard, Papadimitriou 1976. There is not ... more >>>

Recently Ajtai showed that to approximate the shortest lattice vector in the $l_2$-norm within a factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large constant $k$, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor $(1+ \mbox{dim}^{-\epsilon})$, for any $\epsilon>0$, ... more >>>

The bandwidth problem is the problem of enumerating the vertices of a given graph $G$ such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications. There was not much known about approximation hardness of this problem ... more >>>

Given a finite set $S$ of points (i.e. the stations of a radio network) on a $d$-dimensional Euclidean space and a positive integer $1\le h \le |S|-1$, the \minrangeh{d} problem consists of assigning transmission ranges to the stations so as to minimize the total power consumption, provided that the transmission ... more >>>

The Max-Bisection and Min-Bisection are the problems of finding partitions of the vertices of a given graph into two equal size subsets so as to maximize or minimize, respectively, the number of edges with exactly one endpoint in each subset. In this paper we design the first polynomial time approximation ... more >>>

We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known (Khanna, Linial, Safra 1992), but our proof is novel as it does not rely on the PCP theorem, while the earlier one does. This highlights a ... more >>>

An equation over a finite group G is an expression of form w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted variable, or a constant from G; such an equation is satisfiable if there is a setting of the variables to values in G so that the ... more >>>

We study non-Boolean PCPs that have perfect completeness and read three positions from the proof. For the case when the proof consists of values from a domain of size d for some integer constant d >= 2, we construct a non-adaptive PCP with perfect completeness and soundness d^{-1} + d^{-2} ... more >>>

We prove that the subdense instances of MAX-CUT of average degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS). We extend this result also to show that the instances of general 2-ary maximum constraint satisfaction problems (MAX-CSP) of the same average density have PTASs. Our results display for the first ... more >>>

We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some intriguing and still open questions about the approximability status of that problem. Some connections to other optimization problems are also indicated. more >>>

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times. more >>>

We give a reduction from any two-player game to a special case of the Leontief exchange economy, with the property that the Nash equilibria of the game and the equilibria of the market are in one-to-one correspondence. Our reduction exposes a potential hurdle inherent in solving certain families of market ... more >>>

We consider the computational complexity of the market equilibrium problem by exploring the structural properties of the Leontief exchange economy. We prove that, for economies guaranteed to have a market equilibrium, finding one with maximum social welfare or maximum individual welfare is NP-hard. In addition, we prove that counting the ... more >>>

Clique-width is a graph parameter, defined by a composition mechanism for vertex-labeled graphs, which measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic, that includes NP-hard problems) can be solved efficiently for graphs of certified small clique-width. It ... more >>>

Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problems) can be solved efficiently for graphs of certified small clique-width. It is widely ... more >>>

We present an efficient reduction mapping undirected graphs G with n = 2^k vertices for integers k to tables of partially specified Boolean functions g: {0,1}^(4k+1) -> {0,1,*} so that for any integer m, G has a vertex colouring using m colours if and only if g has a consistent ... more >>>

We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short). We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and ... more >>>