Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
693
questions
-1
votes
1
answer
97
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 ...
- 141
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
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 ...
- 20.8k
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 ...
- 103
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$,...
- 23
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 $\...
- 8,234
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
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
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 ...
- 23
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
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 ...
- 133
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 ...
user67795
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 ...
- 3,256
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, ...
- 8,234
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 ...
- 33
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 ...
- 11
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
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 ...
- 11.1k
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 ...
- 98
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?
- 79
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-...
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 ...
- 11
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\...
- 81
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 ...
-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 ...
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 ...
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
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 ...
- 181
1
vote
0
answers
55
views
Find the minimum cost spider joining a root to some leaves
A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider.
I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
- 597
6
votes
1
answer
234
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.
...
- 1,881
0
votes
0
answers
58
views
Are the Eigendecomposition and Singular Value Decompositions in the class P?
I can run, for instance, np.linalg.eig or np.linalg.svd on my computer in polynomial time. However, my understanding is that if the intermediate steps require too many bits to express and give NaNs or ...
1
vote
1
answer
113
views
Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets
In the Exact Cover by 3-Sets problem, we are given a set $X = \{x_1, x_2,\ldots, x_{3n}\}$ and a family of subsets $F = \{\{x_{i_1}, x_{i_2}, x_{i_3}\}\}$ of 3-element subsets of $X$.
The question is ...
- 11
1
vote
1
answer
160
views
Hardness of a class of quadratics
I have a system of inequalities of the form $x_i^2 \le x_j$ with $x_i = a_i + \sum_j \alpha_j b_{i,j}$, the variables are $x_i,\alpha_i$, the values $a_i, b_{i,j} \ge 0$ are known and all $x_i, a_i, \...
- 929
0
votes
1
answer
87
views
Is "choosability of subsets" NP-hard?
Let $n\in\mathbb{N}$ be a positive integer, and let ${\cal A}$ be a collection of subsets of $n=\{0,\ldots,n-1\}$. We say ${\cal A}$ has the choosability property if there is $R\subseteq n$ such that $...
1
vote
0
answers
143
views
Relation between BSS and Turing models
$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine.
Let $0-1-P_\mathbb R=\{...
- 12.6k
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=...
- 57
0
votes
0
answers
90
views
Complexity of the distance between the average vector of two subsets
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors, where $v_i\in \mathbb{R}^d$ is a vector, the target is to select two subsets $V_1=\{v_j\}_{j=1}^{|V_1|} \subset V$ and $V_2=\{v_k\}_{k=1}^{|V_2|...
- 57
2
votes
1
answer
206
views
Complexity of the Complete (3,2) SAT problem?
A complete $k$-CNF formula is a $k$-CNF formula which contains all clauses of size $k$ or lower it implies.
Deciding the satisfiability of a complete $k$-CNF formula is clearly a tractable problem ...
- 1,079
2
votes
0
answers
152
views
Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?
Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, ...
- 8,234
0
votes
0
answers
89
views
What are the capabilities of current Boolean Satisfiability Solvers?
I am wondering how well current Boolean Satisfiability solvers are able to perform — for example, are the best SATsolvers able to solve problems from SATlib?
- 1
2
votes
0
answers
73
views
Prize Box Ordering Problem With Position Constraints: Easy or Hard
I have a problem where we have $n$ boxes, each box $i$ have probability $p_i$ of containing a prize with value $h_i > 0$, and remaining probability of containing nothing. Now we are asked to order ...
- 43
2
votes
1
answer
150
views
Is the weighted sum of subset prefix product problem NP-hard?
I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f: M \rightarrow R^+$ mapping each number in M to another positive number. We want to know ...
- 43
2
votes
0
answers
123
views
SUBSET SUM "with error"
Has a SUBSET-SUM "with error" variant been studied - and with error, I mean, instead of a single target value $k$, a target interval $[k-\varepsilon,k+\varepsilon]$ ($\varepsilon>0$ very ...
- 209
5
votes
0
answers
107
views
Joint Scheduling Problem with Variables Arrival Times
The scheduling problem $1\bigl|r_j\bigl|\Sigma\,U_j$ is strongly NP-hard but when preemption is allowed the scheduling problem $1\bigl|pmtn,r_j\bigl|\Sigma\,U_j$ becomes strongly polynomial.
I have a ...
- 325
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
2
votes
1
answer
287
views
The complexity of 3SAT
It is well known that 3SAT remains NP-complete if every variable occurs exactly twice positively, exactly once negated.
then, does 3SAT remain NP-complete if every variable occurs exactly once ...
- 79
1
vote
0
answers
111
views
Is counting the union of power sets NP-complete?
Say we have $n$ sets $A_1,\dots,A_n$ with elements from a universal set $U$.
We want to compute the cardinality of $\cup_{i=1}^n 2^{A_i}$ or at least decide on non-trivial bounds. Is this problem NP-...
