Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
693
questions
-1
votes
1
answer
98
views
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
There is an ever going trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics.
I have observed, a common trend, to take any sort of ...
- 957
3
votes
0
answers
205
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 11.3k
0
votes
0
answers
83
views
When Exponential Costs are Essential for NP-Hardness?
In many NP-hard problem there is a budget constraint. Each element $e$ in the instance has a certain cost $c(e)$ and a profit $p(e)$; a feasible solution $S$ for the considered problem cannot exceed ...
- 103
1
vote
1
answer
109
views
3 Matroid Intersection, a Special Case
It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard.
Question: Does this problem remain NP-Hard if one of the matroids ...
- 4,367
29
votes
4
answers
5k
views
Implications of unprovability of $P\neq NP$
I was reading "Is P Versus NP Formally Independent?" but I got puzzled.
It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is ...
- 332
0
votes
0
answers
34
views
Reduction of Monotone-1-in-3-SAT to Cubic-Monotone-1-in-3-SAT
3-SAT is an NP-Complete problem. Now given a 3-SAT instance it can be transformed to a Monotone-1-in-3 SAT instance thus even Monotone-1-in-3-SAT is NP-Complete (am aware of this reduction).
But, as I ...
- 314
2
votes
1
answer
56
views
Balls in monochromatic bins
Suppose we have a collection of $m$ balls in $k$ different colors. Let $b_i$ be the number of balls with color $i$, so $\sum_{i=1}^k b_i = m$. Assume we have $n$ bins with capacities $c_1, \dots, c_n$,...
- 11.3k
6
votes
0
answers
85
views
Cycle packing with degree condition
Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard?
Without the degree condition, the ...
- 123
10
votes
1
answer
399
views
Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?
Consider the following decision problem over a fixed alphabet $\Sigma$:
Input: strings $s_1, \ldots, s_n$ of $\Sigma^*$ and a target string $t \in \Sigma^*$
Output: does there exist a permutation $\...
- 255
4
votes
2
answers
180
views
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
- 397
0
votes
1
answer
59
views
Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover
As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size $k$,...
- 135
21
votes
4
answers
1k
views
Complexity of finding a second solution given a correct solution to an NP-complete problem
I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem. More precisely, ...
- 159
19
votes
5
answers
2k
views
Why is it important to prove that a problem is NP-complete?
Am I correct in understanding that proving a problem NP complete is a research success? If so why?
- 159
13
votes
5
answers
2k
views
Is the feedback vertex set problem on planar bounded degree graphs hard?
Is it known whether the feedback vertex set problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?
- 2,560
2
votes
1
answer
106
views
NP-complete problems on posets?
I'm in the midst of some doctoral research and trying to figure out a particularly tricky reduction. I think my best shot is to reduce from an NP-complete problem on posets, if one exists.
I did some ...
- 1,798
11
votes
1
answer
455
views
Recent progress on the next-to-shortest-path problem for directed graphs?
In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem:
Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be vertices in ...
CommunityBot
- 1
0
votes
1
answer
170
views
The Complexity of Multi-Objective Optimization
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
CommunityBot
- 1
9
votes
1
answer
893
views
NP-Hardness of a special case of orthogonal packing problem
Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used ...
- 159
13
votes
1
answer
326
views
Is this a known problem, and is it NP-complete?
Does the following problem have a name? Is it NP-complete?
Given a multiset of $n$ positive integers, $S$, and an positive integer $m$, does there exist an $m \times n$ matrix whose rows are ...
- 1,657
10
votes
0
answers
139
views
Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$
Suppose we have a graph $G$ with maximum degree $\Delta$. Deciding if $G$ can be colored with $\Delta$ colors is easy: Brooks' theorem says that this is always possible, unless $G$ is a clique or an ...
- 3,256
8
votes
1
answer
222
views
Is it $NP$-hard to check whether a given algebraic circuit computes permanent?
Given are a natural number $n\in\mathbb{N}$ and a polynomial $P$ in the form of an arithmetic circuit $C$ over $\mathbb{Z}$ (a circuit which only uses $+$ and $\times$ gates and integer constants as ...
CommunityBot
- 1
4
votes
2
answers
417
views
Random self reducibility and NP
I was reading the Wikipedia page Random self-reducibility and it states:
If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$.
I am ...
CommunityBot
- 1
2
votes
0
answers
52
views
hardness of partition of permutation into a minimum number of monotone subsequences
Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
- 71
6
votes
1
answer
115
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 ...
- 1,537
4
votes
1
answer
98
views
Complexity of finding a path visiting all leaves on a tree while respecting a distance bound
I am interested in the complexity of a specific variant of the Hamiltonian path problem where we want to visit all leaves of a tree while respecting a distance bound. Formally, given an (undirected, ...
- 1,272
50
votes
4
answers
14k
views
Is finding the minimum regular expression an NP-complete problem?
I am thinking of the following problem:
I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses).
...
- 159
0
votes
1
answer
75
views
increasing minimum graph degree by adding edges
My problem: Given a graph $G=(V, E)$ and an integer $\ell$,add a minimum number of edges to $G$ so that in the resulting graph every vertex has degree at least $\ell$.
Is there a polynomial-time ...
- 9,545
1
vote
2
answers
132
views
Is this subsequence problem NP-hard?
Here is yet another "is X NP-hard?" question.
The input of the problem is the following:
A sequence of $n$ non-negative real numbers $\alpha_1, \ldots, \alpha_n$. Here $n$ is a positive ...
- 111
8
votes
3
answers
674
views
Is that 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{u\in V} ~\left( d_{...
- 9,545
3
votes
1
answer
296
views
Is this node permutation optimization NP-Hard?
Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in ...
- 121
2
votes
0
answers
111
views
Computing real numbers with Turing Machines
Consider the following decision problem:
Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$
Question: Is this problem known to be in $P$?
Although this may look like a stupid ...
- 475
52
votes
20
answers
9k
views
NP-hard problems on trees
Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
- 4,381
2
votes
1
answer
123
views
Optimal solution for partitioning convex polygon
Given a convex polygon $P$ (possibly) with holes. We want to partition $P$ into a minimum number of connected interior-disjoint polygons $P_1,...P_s$. The definition of restriction on the pieces is ...
- 133
4
votes
1
answer
176
views
Finding a "typical" path
Consider an undirected graph with two distinguished nodes $u\neq v$. How hard is it to find an $u-v$ path, such that its length is as close to the average $u-v$ path length as possible?
Formally, for ...
- 9,545
7
votes
1
answer
172
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 ...
- 9,545
2
votes
1
answer
91
views
Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth
Whether there is a problem to meet the conditions: it is polynomial time solvable in series parallel graphs but NP-hard in graph with bounded treewidth?
- 50.6k
15
votes
1
answer
943
views
Integer relation detection for Subset Sum or NPP?
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
- 159
0
votes
0
answers
51
views
Existence of W[1]-Hard construction from multiple hard problems
I am a research scholar working on parameterized complexity. Currently, I am exploring ways to prove the hardness of a problem by providing W[1]-Hard constructions. A problem is known to be fixed-...
28
votes
6
answers
3k
views
Are there NP-complete problems with polynomial expected time solutions?
Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)?
If not, are there problems for ...
- 355
16
votes
0
answers
420
views
Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?
I am interested in the following problem.
Node Multiway Cut on Planar Graphs with terminals on the outer face
Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals which ...
- 355
1
vote
1
answer
65
views
Running time of SAT and other EXPTIME algorithms [closed]
I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time $O(2^s\cdot n^2), s\leq n.$ The algorithm aims to finding a path in a graph $G(V, E)$ (in ...
- 1,034
2
votes
0
answers
116
views
Complexity of a sum with a product
Is the following problem NP-complete:
Input: A set of tuples $T = \left\{ t_i=(a_i,b_i) | 1\le i\le n \right\}$, an integer $k$ and numbers $C,D\in \mathbb Q_{\ge 0}$.
Question: Exists a subset $S\...
- 2,723
0
votes
0
answers
82
views
Parameterized intractability for Twin cover
I am currently working on Parameterized algorithms, especially on the complexity of the given problem when parameterized by twin cover as the parameter. I have read the following papers on formulating ...
39
votes
4
answers
3k
views
Techniques for showing that problem is in hardness "limbo"
Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this ...
- 20.8k
6
votes
0
answers
138
views
Computing Sequences with Addition Chains In pseudopolynomial time?
Computing Sequence $a_1, \ldots, a_n$ with addition chains (CSAC) is the problem of finding the shortest sequence $b_1, \ldots, b_m$ with the following properties:
$b_1=1$.
Every $b_i$ with $i>1$ ...
- 1,881
-1
votes
1
answer
101
views
Parameters: Twin cover and Vertex cover
I am a research scholar, currently working on parameterized algorithms. I am working on a problem and have been exploring various parameters for which the problem remains unsolved. I have read the ...
- 2,723
0
votes
0
answers
74
views
Tractability with respect to multiple parameters
I am working on the decision version of an NP-complete problem. The problem is known to be fixed parameter tractable(FPT) with respect to the solution size $k$ as the parameter.
If I consider another ...
- 2,723
7
votes
2
answers
1k
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 ...
- 111
17
votes
1
answer
1k
views
Ranking the Difficulty of NP Hard Problems in Practice
This question is tightly related to another post: Phase Transitions in NP Hard Problems but it is somewhat different. While that question is about the hardness of particular instances of NP hard ...
- 355
4
votes
2
answers
346
views
NP-hard problem which is easy on average
I have a feeling like I read somewhere that the Hamiltonian circuit problem is NP-hard, but it is easy on average, or easy for a random instance. However, I cannot find a reference for that, nor an ...
- 2,723