Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NP-HARDNESS:
Reports tagged with NP-hardness:
TR96-016 | 6th February 1996
Andrea E. F. Clementi, Luca Trevisan

Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints

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 ... more >>>


TR96-028 | 9th April 1996
Sanjeev Khanna, Madhu Sudan

The Optimization Complexity of Constraint Satisfaction Problems

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 >>>


TR97-024 | 9th June 1997
Marek Karpinski

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems

We survey recent results on the existence of polynomial time
approximation schemes for some dense instances of NP-hard
optimization problems. We indicate further some inherent limits
for existence of such schemes for some other dense instances of
the optimization problems.

more >>>

TR97-041 | 18th September 1997
Marek Karpinski, Juergen Wirtgen

On Approximation Hardness of the Bandwidth Problem

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 ... more >>>


TR97-059 | 22nd December 1997
Jin-Yi Cai, Ajay Nerurkar

Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions

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 >>>


TR98-014 | 6th February 1998
Gunter Blache, Marek Karpinski, Juergen Wirtgen

On Approximation Intractability of the Bandwidth Problem

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 ... more >>>


TR00-043 | 21st June 2000
Uriel Feige, Marek Karpinski, Michael Langberg

A Note on Approximating MAX-BISECTION on Regular Graphs


We design a $0.795$ approximation algorithm for the Max-Bisection problem
restricted to regular graphs. In the case of three regular graphs our
results imply an approximation ratio of $0.834$.

more >>>

TR00-054 | 5th May 2000
Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

On the power assignment problem in radio networks

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 ... more >>>


TR00-064 | 29th August 2000
Klaus Jansen, Marek Karpinski, Andrzej Lingas

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

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 ... more >>>


TR00-073 | 28th August 2000
Venkatesan Guruswami, Sanjeev Khanna

On the Hardness of 4-coloring a 3-colorable Graph

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 ... more >>>


TR02-030 | 3rd June 2002
Lars Engebretsen, Jonas Holmerin, Alexander Russell

Inapproximability Results for Equations over Finite Groups

Revisions: 1

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 ... more >>>


TR02-040 | 20th June 2002
Lars Engebretsen, Jonas Holmerin

Three-Query PCPs with Perfect Completeness over non-Boolean Domains

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
more >>>


TR02-044 | 16th July 2002
Wenceslas Fernandez de la Vega, Marek Karpinski

A Polynomial Time Approximation Scheme for Subdense MAX-CUT

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 ... more >>>


TR02-046 | 16th July 2002
Marek Karpinski

On Approximability of Minimum Bisection Problem

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 >>>

TR04-111 | 30th November 2004
Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

Computational Complexity of Some Restricted Instances of 3SAT

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

more >>>

TR05-055 | 19th May 2005
Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

Leontief Economies Encode Nonzero Sum Two-Player Games

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 >>>


TR05-074 | 8th June 2005
Li-Sha Huang, Xiaotie Deng

On Complexity of Market Equilibria with Maximum Social Welfare

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 >>>


TR05-080 | 21st July 2005
Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Proving NP-hardness for clique-width I: non-approximability of sequential clique-width

Revisions: 1

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 >>>


TR05-081 | 21st July 2005
Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Proving NP-hardness for clique-width II: non-approximability of clique-width

Revisions: 1

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 >>>


TR06-004 | 6th January 2006
Jesper Torp Kristensen, Peter Bro Miltersen

Finding small OBDDs for incompletely specified truth tables is hard

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 ... more >>>


TR10-031 | 4th March 2010
Christian Gla├čer, Christian Reitwie├čner, Heinz Schmitz, Maximilian Witek

Hardness and Approximability in Multi-Objective Optimization

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 >>>


TR12-020 | 3rd March 2012
Daniele Micciancio

Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

Revisions: 1

We prove that the Shortest Vector Problem (SVP) on point lattices is NP-hard to approximate for any constant factor under polynomial time reverse unfaithful random reductions. These are probabilistic reductions with one-sided error that produce false negatives with small probability, but are guaranteed not to produce false positives regardless of ... more >>>


TR12-151 | 6th November 2012
Subhash Khot, Madhur Tulsiani, Pratik Worah

The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-satisfiable instance of the MAX-$k$-CSP$(f)$ problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let $\tau(f)$ denote ... more >>>


TR13-115 | 27th August 2013
Daniele Micciancio

Locally Dense Codes

The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>>


TR14-108 | 10th August 2014
Andrej Bogdanov, Christina Brzuska

On Basing Size-Verifiable One-Way Functions on NP-Hardness

Revisions: 1

We prove that if the hardness of inverting a size-verifiable one-way function can
be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This
claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but
was later retracted (STOC 2010).

more >>>

TR18-030 | 9th February 2018
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... more >>>




ISSN 1433-8092 | Imprint