Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
20
votes
1answer
831 views

Is finding Logspace reductions harder than P reductions?

Motivated by Shor's answer related to different notions of NP-completeness, I am looking for a problem that is NP-complete under P reductions but not known to be NP-complete under Logspace reductions (...
11
votes
1answer
215 views

maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph

Has this problem been studied before? Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the ...
3
votes
0answers
234 views

A version of bipartite graph turnpike problem

Given a set of "required" weights for edges of a bipartite graph, I am looking for assignments to the nodes so that there is at least an edge carrying a weight from that set. Each edge can have ...
10
votes
2answers
575 views

Exact exponential-time algorithms for 0-1 programming

Are there known algorithms for the following problem that beat the naive algorithm? Input: A system $Ax \le b$ of $m$ linear inequalities. Output: A feasible solution $x^*\in \{0,1 \}^n$ if ...
8
votes
2answers
357 views

Complexity of the $(3,2)_s$ SAT problem?

Let define the $(3,2)_s$ SAT problem : Given $F_3$, a satisfiable 3-CNF formula, and $F_2$, a 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable? What ...
5
votes
0answers
114 views

Variation on block design/set cover

Given 3 parameters $s, r$ and $t$, where $r \leq t$, I want to construct $t$ sets such that each integer $\{1, \ldots, s\}$ appears in exactly $r$ of these sets. The question is: Is it possible to ...
7
votes
2answers
363 views

Complexity of a variant of the max word problem. NP-complete?

I'd like to be able to state that the following problem is NP hard. I am wondering whether anybody have any pointers to related/recent work? The problem: Given a finite set of transition matrices $A$ ...
6
votes
1answer
286 views

Complexity of finding large grid minors

What is the complexity of finding the largest $k\times k$ grid graph that is a minor of a given graph $G$? It is FPT in $k$, and it seems likely to be NP-hard (or NP-complete in a decision version ...
12
votes
1answer
2k views

Efficient algorithm for existence of permutation with differences sequence?

This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations. A differences sequence $a_1, ...
7
votes
2answers
412 views

Binary matrix column subset selection complexity

Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no ...
29
votes
2answers
2k views

Can you identify the sum of two permutations in polynomial time?

There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question: Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
13
votes
1answer
200 views

What is the minimum required depth of reductions for NP-hardness of SAT?

As everyone knows, SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions. It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions. My questions is what is the minimum ...
7
votes
1answer
660 views

The computational complexity of spectral norm of a matrix

How hard is computing the spectral norm of a matrix? This paper says, ... it suffices to say that, except for few particular cases, the Matrix Norm problem is NP-hard. I expected that the ...
8
votes
1answer
644 views

What is complexity of this max-edge subgraph problem?

While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below: Given a connected undirected graph, finding a maximum-...
9
votes
3answers
685 views

Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

Suppose P != NP. We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there ...
17
votes
1answer
1k views

Complexity of interval cover problem

Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to ...
18
votes
0answers
503 views

Complexity of the densest $k$-subgraph problem on planar graphs

In the densest $k$-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is ...
0
votes
1answer
243 views

PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem

Problem 1 I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a polynomial time ...
6
votes
2answers
341 views

Decision problem related to coloring

Given a $k$-colorable graph $G$ and vertices $u$ and $v$ of $G$, what is the complexity of deciding if every $k$-coloring of $G$ must assign the same color to both $u$ and $v$? It does not seem ...
17
votes
1answer
895 views

What is the complexity of this edge coloring problem?

Recently, I have encountered the following variant of edge coloring. Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying ...
33
votes
2answers
3k views

Reference for NP-hardness of 3-colouring?

I have a historical question. I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard. The tempting answer ...
0
votes
1answer
224 views

Is there any reference on the hardness of approximation for 2-partition problem?

I tried to look for some references but could not find any. I knew it is proved to be NP-complete via a transformation from Knapsack or 3DM problem. But I couldn't find a way to apply PCP theorem to ...
2
votes
0answers
190 views

Reduction from OR-SAT to Exact CNF-SAT, keeping the number of variables polynomially bounded?

Let me define both the problems first: $OR$-$SAT$: $m$ Boolean formulae are given in $CNF$, $\phi_1$,$\phi_2$, $\ldots$, $\phi_m$, each on variable set, $x_1, x_2, \ldots, x_n$. ($m$ $<$ $2^n$, ...
4
votes
1answer
223 views

Complexity reductions to Hamiltonian Path?

I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path. Do ...
6
votes
3answers
705 views

The Drawing Challenge - a problem I made up and can't solve!

I made up the following problem but have not made any headway in solving it in anything less than exponential time. Hopefully somebody can shed some light on it. I'm starting to think it may be $\sf{...
14
votes
1answer
1k views

How can a problem be in NP, be NP-hard and not NP-complete?

For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP. However, in the famous paper "The ellipsoid method and its consequences in ...
12
votes
1answer
3k views

How hard is binary Sudoku puzzle?

Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers $0$ and $1$. The rules are as follows. Each row and each column must contain an equal number ...
2
votes
0answers
70 views

Small area containing large amount of patterns

The problem: I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times ...
3
votes
0answers
242 views

Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables

Integer programing is one of the most narutal optimization tools. As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation. $x_{1}x_{2}x_{3}+$ $x_{3}x_{4}x_{...
15
votes
3answers
3k views

Subset sum vs. Subset product (strong vs. weak NP hardness)

I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard. Subset Sum: Given $X = \{x_1,...,...
8
votes
3answers
1k views

P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
13
votes
1answer
731 views

Intermediate $\mathsf{NP}$-complete problems?

Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition is strongly NP-complete ...
1
vote
0answers
241 views

What are the consequences of a ${\bf O}$(m) algorithm for SAT

We are given a Boolean formula $F$ in conjunctive normal form with $n$ variables and $m$ clauses and we would like to know if there exists at least one assignment to the $n$ variables that makes $F$ ...
8
votes
1answer
548 views

Fitting minimum number of rectangles of width/height 1 into a 2D grid

Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied and you need to put the minimum number of non-overlapping rectangles of any size w x h where ...
7
votes
1answer
389 views

$NP$-hardness of scheduling problem

I have been attempting to show that this problem is $NP$-complete but haven't been successful. I wonder if anyone has a suggestion for a problem I could reduce to it. $CALLS$: Suppose we have ...
16
votes
1answer
378 views

Natural candidates for the hierarchy inside NPI

Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems ...
11
votes
4answers
2k views

List of strongly NP-hard problems with numerical data

I am looking for strongly NP-hard problems for a reduction. So far I have found the following problems: 3-partition problem bin-packing problem Numerical 3-dimensional matching TSP Any NP-complete ...
5
votes
1answer
772 views

Computational Complexity of Computer Vision Problems

What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard? In most cases this will boil down to determining ...
7
votes
0answers
160 views

Universal tractable problem solver

Consider $X$ an $\mathsf{NP}$-complete language e.g. $3-SAT$. I'm looking for an algorithm $A$ for solving $X$ with the following property. Given $M \subset \lbrace 0, 1 \rbrace^*$ any set of words s....
9
votes
1answer
840 views

Does every Turing-recognizable undecidable language have a NP-complete subset?

Does every Turing-recognizable undecidable language have a NP-complete subset? The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
2
votes
0answers
252 views

Is this variation of the “sequencing with release times and deadlines” problem NP-complete?

The following problem is known to be NP-complete. It can be found in pages 236 and 70 of Garey & Johnson. In this book this problem is known either as ...
3
votes
1answer
113 views

Is there an algorithm that's “like” cross-validation for approximation algorithms of NP-hard problems?

I normally do machine learning work, and when I'm evaluating an algorithm on a data set, I always use cross-validation to determine how effective the algorithm is. Is there a similar method for ...
28
votes
2answers
1k views

When does “X is NP-complete” imply “#X is #P-complete”?

Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version. Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"? Of course the existence ...
7
votes
0answers
193 views

What is the complexity of pallet loading for identical non-rectangular objects?

In the pallet loading problem, we are asked to place a set of small identical 2-D rigid objects into a large bounding rectangle such that no two objects overlap. This problem is a special case of the ...
11
votes
4answers
768 views

Does NP-completeness/hardness have to be constructive?

Is there any $L\in {\bf NP}$ with the following properties: It is known that $L\in {\bf P}$ implies ${\bf P}={\bf NP}$. There is no (known) polynomial time Turing reduction of $SAT$ (or some other ${\...
8
votes
1answer
371 views

NP-hardness of an optimization problem

While studying a problem in algorithmic game theory I got interested in the complexity of the following optimization question: Problem Given: ground set $U = [n] = \{1,\ldots,n\}$ given by $n$, $...
22
votes
1answer
539 views

Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3?

Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, ...
-3
votes
1answer
116 views

Difference between 'Reductions' in algebraic problems vs “Reductions” in Computational Intractability [closed]

When I read NP-completeness for the first time, I really wondered why is the concept of Reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special ...
8
votes
1answer
325 views

The complexity of the puzzle game Net

Net (known also as FreeNet, or as NetWalk) is a puzzle game played on a $n \times n$ grid with the following objects: there are $m$ computers ; each computer occupies one cell and has one link cable; ...
17
votes
2answers
1k views

The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness

The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem. However, in the ...