Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
732
questions
7
votes
2
answers
675
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 ...
- 295
7
votes
1
answer
485
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 ...
- 233
7
votes
2
answers
357
views
What is known about the H-factor problem?
Background
The $\mathcal{H}$-factor problem (a.k.a. the degree prescribed factor problem, or the degree prescribed subgraph problem) is defined as follows:
Given a graph $G=(V,E)$ and a set $H_v \...
- 4,258
7
votes
1
answer
456
views
Techniques for proving NP completeness for a specific sequence of instances
Most NP-completeness proofs I have seen pertain to proving that a problem on a class of instances is NP-complete. E.g., satisfiability is NP-complete on the class of instances with clauses having ...
- 779
7
votes
1
answer
212
views
Is Clique completion for intersection models hard?
The following seems like a natural problem and I'm surprised I can't find any literature on it... but maybe it's because I don't know the name for it.
Given a list of sets $S_1, S_2, S_3, \ldots$
...
- 1,316
7
votes
1
answer
353
views
Is solving the following system of boolean equations NP-hard?
I reduced a problem I'm currently working on to the following system of boolean equations:
$$
X_i \iff
\begin{cases}
\bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\
true \\
false
\end{cases}
$$
Where $|...
- 173
7
votes
1
answer
253
views
What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?
Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (...
- 1,572
7
votes
1
answer
222
views
What are the hardness results known for CSP over $\mathbb{F}_q$?
I found two related papers,
There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf
A kind of a stronger result might be found in these two other papers, http://...
- 1,453
7
votes
1
answer
1k
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 ...
- 831
7
votes
1
answer
4k
views
Simple reduction to unbounded knapsack?
Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited ...
- 1,520
7
votes
1
answer
184
views
Complexity of Maximizing Hamming Distances Below a Threshold
Problem Statement
Is the following problem NP-Complete?
Input: A collection $S$ of binary strings, with each string of length $m$.
Goal: Compute a binary string $s^*$ of length $m$ that mazimizes the ...
- 98
7
votes
1
answer
295
views
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
My question concerns the NP-hardness of the following discrete optimization problem:
Given a matrix $A \in \{ \pm 1 \}^{m\times n}$,
$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm ...
- 73
7
votes
1
answer
1k
views
Is it NP-hard to _play_ minesweeper perfectly?
This paper shows that it is NP-hard "to determine if there is some pattern of mines in the blank squares that give rise to the numbers seen."
If there is a way to "lead a perfect player into" such ...
user6973
7
votes
1
answer
136
views
Complexity of selective network improvement problem
We have a network flow problem with a given directed graph $G=(V,E)$, for each arc $(i,j) \in E$, there is a cost $c_{ij}$ and upper and lower capacity $u_{ij}$ and $l_{ij}$ for the flow $f_{ij}$ ...
- 283
7
votes
1
answer
387
views
Complexity of constructing minimum depth decision trees
I am interested in the computational complexity of
Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
- 193
7
votes
1
answer
257
views
Complexity of a graph-rewriting problem
I recently came across the following problem which seems to fall in the context of graph rewriting problems:
Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(...
- 607
7
votes
3
answers
738
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{...
- 209
7
votes
1
answer
321
views
Is sorting NP-complete?
SORTING problem.
Input: A poset which corresponds to a partially sorted list of different numbers.
Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array.
...
- 14k
7
votes
0
answers
245
views
How hard is PromiseFlowFree?
Playing more Flow Free, I think I've realized why I'm so amazingly brilliant at this game:
The objective is to connect all pairs while covering the entire board, but in every puzzle there is always ...
- 14k
7
votes
0
answers
517
views
On the shortest vector problem (is it $NP$-complete?)
Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum.
Has this been derandomized?
- 12.9k
7
votes
0
answers
3k
views
Reduction from Vertex Cover to Max-Cut? [closed]
I am referring to Computational Complexity by Arora and Barak for my course. In the section on NP-completeness reductions, the book has a diagram that is represents how one NP-complete problem ...
- 227
7
votes
0
answers
166
views
What relations are there between a problem hardness and the hardness of verifying a witness?
I had some hard times trying to formulate the question, so I'll start with some examples:
Suppose you are given a Dominating Set instance, $<G,k>$.
Now suppose I give you a set of vertices $D$ ...
- 9,448
7
votes
0
answers
573
views
Another Solution Problem (ASP) of integer multi-commodity flow: is it NP-complete?
I know that integer multicommodity flow is NP-complete. It was proven in
On the complexity of time table and multi-commodity flow problems
that any SAT problem can be reduced to an integer ...
- 71
7
votes
0
answers
168
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....
- 2,151
7
votes
0
answers
222
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 ...
- 640
6
votes
3
answers
1k
views
Complexity of a subset sum variant
Given integers $a_1, \ldots, a_n, b \in \mathbb{N}$. What is the complexity of the following problem
$$
\exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b?
$$
I ...
- 61
6
votes
1
answer
4k
views
Guidelines to reduce general TSP to Triangle TSP
I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie:
$D(a, b) \leq ...
- 71
6
votes
3
answers
2k
views
Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?
Good Evening!
I am aware that the minimum (cardinality) vertex cover problem on cubic graphs ($3$-regular) graphs is $NP$-hard. Say positive integer $k>2$ is fixed. Has there been any ...
- 63
6
votes
3
answers
903
views
In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
I have doubt whether the problem mentioned can be solved in polynomial ...
- 467
6
votes
1
answer
305
views
NP-hardness of coloring uniform hypergraphs
Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen ...
- 407
6
votes
1
answer
372
views
Maximum Polyhedron Volume in Given $n$ Points
Suppose we are given $n$ points $v_1,v_2,\cdots, v_n\in \mathbb{R}^k$, I want to find $k+1$ points $v_{i_1}, v_{i_2},\cdots,v_{i_{k+1}}$ such that the volume of the convex body spanned by them ...
- 271
6
votes
3
answers
447
views
Finding a minimal context free grammar that recognizes a finite set of strings of bounded length
Problem:
Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that ...
- 1,132
6
votes
1
answer
548
views
What is the complexity of vertex cover on k-partite graphs?
Given a k-partite graph which is already partitioned into k parts,
what is the complexity of finding a vertex cover of minimum size?
I guess that it's NP-hard, but couldn't yet prove it or find ...
- 63
6
votes
1
answer
346
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 ...
- 51k
6
votes
1
answer
913
views
Does there exist the idea of "RP-complete", like NP-complete?
NP-hardness and NP-completeness play an important role in complexity theory.
My question is, does there exist a language $L$ in RP
to which any language $M$ in RP can be reduced in polynomial time?
...
6
votes
1
answer
465
views
Comparing $\mathbf{NP}$ and $\mathbf{E}$
We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$.
The complexity zoo states that $\mathbf{E}$ does not equal $\mathbf{NP}$, and cites the following ...
- 16.5k
6
votes
1
answer
290
views
Why does Dinur's proof of the PCP theorem fail to work for unique games?
What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap ...
- 61
6
votes
2
answers
261
views
Kth best problem that is NP-hard for K polynomial
A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to ...
- 109
6
votes
1
answer
247
views
NP-completeness of a problem using a "T-gadget"
Working on a problem I came up with the following "T-gadget":
It has 3 connectors (A, B, C); each connector has two wires (A1,A2; B1,B2; C1,C2);
it can be rotated (0, 90, 180, 270 degrees);
two ...
- 23k
6
votes
1
answer
223
views
Minimal generator for a set of sets
Is this a known problem?
Given a set of sets $S$ find a set of sets $B$ s.t. each set in $S$ can be obtained through unions of some sets in $B$. The set $S$ is already a solution but the objective is ...
- 1,322
6
votes
1
answer
262
views
totally-mixed 2SAT with exact cardinality?
Given a 2HornSAT problem, it’s possible in linear time to find the minimum solution to the problem, i.e., a solution that minimizes the number of variables set to 1.
Now let us consider the following ...
- 811
6
votes
1
answer
140
views
Complexity of induced Steiner Tree problem
Consider the following problem: we are given an undirected graph $G=(V,E)$ and three terminal vertices $t_1,t_2,t_3\in V$. We are asked whether there exists a set of vertices $S\subseteq V$ such that ...
- 3,698
6
votes
1
answer
1k
views
For what k is MAX-2-SAT-k NP-complete?
It is well-known that it is NP-complete to decide whether in a 2-CNF at least s clauses are satisfiable. It also follows from the reduction from 3-SAT-3 that we can suppose that every literal occurs ...
- 14k
6
votes
1
answer
125
views
NP completeness of classes of spanning trees
I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete.
This made me think of the following problem: does ...
- 359
6
votes
1
answer
242
views
Graph class with easy chromatic number, but NP-hard coloring
Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard?
Without any further restriction the answer ...
- 11.4k
6
votes
1
answer
264
views
Finding a minimal addition chain for a given number
An addition chain for computing a positive integer $n$ is a sequence of natural numbers starting with $1$ and ending with $n$, such that each number in the sequence is the sum of two previous numbers.
...
- 2,003
6
votes
1
answer
372
views
Is this edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\...
- 563
6
votes
2
answers
172
views
$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$
Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
- 71
6
votes
1
answer
552
views
Graph partitioning by node deletion
Given an undirected graph and an integer $B$,
we ask to find the minimum set of nodes
whose removal partitions the generated graph into connected components,
each having at most $B$ nodes.
We can ...
- 61
6
votes
2
answers
718
views
Edge and vertex fault tolerance in graphs
Suppose we are given two graphs $G$ and $H$, where $H$ is a subgraph of $G$. What is the maximum number $k$ such that if any $k$ edges are removed from $G$, $H$ still remains a subgraph of $G$? What ...
- 1,591