Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
595
questions
1
vote
0answers
28 views
Is Partition Problem with non-integer input NP-complete?
The Partition Problem supposes that we have a set $S=\{s_{i} \in \mathbb{R^{+}}\}_{i=1}^{n}$, is there a subset $T$ such that $\sum_{s \in T} s = \sum_{s \notin T}s$?
I have read a lot of proofs using ...
0
votes
1answer
42 views
Are most machine learning problems the same problem? (NP-hard)
I am trying to teach P vs NP to some primarily Machine Learning folks. I wanted to come up with an introductory fact to grab their attention.
Reasoning for Question:
Most problems in Machine Learning ...
1
vote
1answer
21 views
What is a good reference for NP hardness in the machine learning/optimization/operations research context?
I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:
Theorem 1.1. For any constant ϵ > 0, it is NP-hard ...
0
votes
1answer
34 views
If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?
This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor?
Let's take the Traveling ...
0
votes
1answer
29 views
Algorithm for assigning people to groups
Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that:
every element of $L$ is assigned to exactly one group
$g_k = (L_i, L_j) \...
3
votes
1answer
42 views
How difficult is this matching-like problem?
Let $A$ and $B$ be two sets of integers with $|A|>|B|$.
Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am ...
1
vote
1answer
38 views
How to find a cut in a graph with additional constraints?
I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$.
I would ...
0
votes
1answer
67 views
Hardness of maximizing difference of functions
Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP_HARD. What can be said about the problem of maximizing $f-g$, with $g$ being another function over $D$? Is it ...
2
votes
1answer
71 views
Finding a boolean submatrix isomorphic to a specific fixed set of other boolean matrices
Given a matrix $M$ of certain size $h\times w$, where $h\leq w$, for example $5\times 6$, are also given the following set $B$ of additional all-ones matrices, that I like to call target (b)oxes.
$$
\...
1
vote
3answers
677 views
Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?
Question
Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?
The adding a parameter is needed ...
2
votes
2answers
424 views
Definition of NP-hardness for non-decision problems
As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-...
2
votes
1answer
103 views
If P=NP, does this imply that all problems are NP-hard?
A problem is said to be NP-hard if every problem in NP is reducible to that problem in polynomial time.
Hence, if P=NP, wouldn't that imply that every problem in NP is reducible to every possible ...
0
votes
0answers
17 views
Offline bin-packaging problem: probability of a non-optimal solution for the first-fit-decreasing algorithm
For the offline bin packaging problem (non-bounded number of bins, where each bin has a fixed size, and a input with known size that can be sorted beforehand), the first-fit-decreasing algorithm (FFD) ...
0
votes
1answer
16 views
Multi-dimensional Knapsack with Minimum Value constraints for Dimensions
In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.
I want to add a conditional constraint: $V = {...
0
votes
0answers
47 views
Is a or free SAT formula NP complete?
Let $L$ be the languague which contains all satisfiable formulas which do not have the or symbol $\lor $.
Or more precise $$L=\{\phi | \phi \text{ is a satisfable formula which is only using the ...
3
votes
1answer
67 views
Algorithm to compute average length of a simple path
Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t. Is there an efficient algorithm to find the average length of these paths?
2
votes
2answers
132 views
Is $EVEN-SAT$ $NP$-hard?
I'm looking for an $NP$-hardness proof for the following variant of $SAT$:
$$
EVEN-SAT = \{\langle \phi \rangle: \phi \text{ has an even number of satisfying assignments}\}
$$
I've been playing around ...
1
vote
1answer
71 views
Is protein folding NP-hard and how to prove that?
This question has two facets that are related.
Is the general problem of protein folding really NP-hard?
The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a ...
7
votes
1answer
247 views
Is the buckets of water problem in NP?
Continuing from this question: the buckets of water problem.
(All the definitions can be found there, so I will not repeat them).
As seen there by Yuval's answer, the problem is NP-Hard.
I was ...
2
votes
1answer
177 views
Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset
I am working on a problem defined as the following
Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our ...
2
votes
2answers
70 views
Is realization of unit disk graphs hard?
It is known that recognizing a unit disk graph is NP-hard [1].
However, the paper does not mention how hard the realization problem is.
I have looked up several references [2][3][4]. None of the ...
0
votes
0answers
50 views
Find every path that passes through certain edges
I'm faced with the following problem:
Given
Directed and unweighted graph, where each edge E has two attributes
Goal
Find every path through the 3 (or more) given edges in a specific order
...
0
votes
1answer
70 views
What complexity class is the TSP problem?
Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?
0
votes
0answers
16 views
Given L1 and L2 in NP, if L1 transforms L2 and L2 transforms HC then L1 NP complete?
Why this Question is False ?
NP-complete problems are the hardest problems in NP.
if L is in NP-complete then [L must be in NP, all problems in NP can be transformed to L].
Does this mean that L2 ...
0
votes
1answer
64 views
How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem
I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t:
...
5
votes
1answer
65 views
Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope
I want to solve a linear programming problem in the $2n$ variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ where the cost is of the form $x_1/y_1 + \cdots + x_n/y_n$. Specifically, I want to solve
\...
4
votes
1answer
153 views
Prove finding k disjoint paths from n given paths in a directed graph is NP-complete
Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node.
Prove that the given problem is in NP-complete.
...
3
votes
1answer
90 views
Having trouble understanding a proof of Mahaney’s theorem
I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.
I am not sure why $a’$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $a’$ cannot be in between $...
0
votes
1answer
55 views
Polynomial-time reduction of Primality and 3-SAT
Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.
Thank you.
1
vote
1answer
50 views
Reducing independent set to triangle-free subgraph
The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$.
An instance of the TFS (...
1
vote
0answers
29 views
How to the NP hard of a problem that search for a subset of points with maximum scores?
Suppose in a plane, there is a set of points, whose distance to $(0,0)$ is always 1:
$[(0,1),(1,0),(0.707,0.707),(0.707,-0.707),...]$
Each point is assigned with a weight (possible negative):
$[w(...
0
votes
2answers
62 views
2D packing in fixed dimensions rectangle
Input:
a enclosing rectangle of size $(W, H)$
a family of rectangles $R= (R_1;R_2;\dots;R_n);R_i=(w_i;h_i)$
Output:
a scaling factor $s$
a 2D bin packing of $R$ in a rectangle of size $(sW, sH)$
I ...
1
vote
1answer
139 views
How to prove finding two paths that are at least k edges apart is NP-hard?
Let $G=(V, E)$ be an unweighted, undirected, and connected graph. Given two start vertices $s_1$ and $s_2$ and two end vertices $t_1$ and $t_2$ is there a path from $s_1$ to $t_1$ and $s_2$ to $t_2$ ...
2
votes
2answers
222 views
Disjoint union of NP-hard problem and P problem is NP-hard
Let $Σ = \{0, 1\}$ and let $A, B ⊆ Σ^*$ be languages. Prove that if $A$ is NP-hard, $B$ is in P,
$A ∩ B = ∅$, and $A ∪ B ≠ Σ^*$, then $A ∪ B$ in NP-hard.
How can I go about proving $A ∪ B$ is NP-...
0
votes
0answers
14 views
Search reduction to decision
I'm a little stumped on this question (and I don't know the name of it, which is why I've excluded it from the title). I need to describe an algorithm that finds a solution to an NP-Hard problem given ...
1
vote
0answers
72 views
Prove that a 3D packing problem is NP-complete
How can I prove that the following problem is NP-complete?
I have a spherical container in which I have to introduce $n$ identical spheres. All of the little spheres have to be inside the container ...
0
votes
2answers
40 views
Is the complexity of problems in NP exponential at most?
I read on Wikipedia the following:
Since NP-complete problems are in NP, their running time is at most exponential.
Is that correct? I thought a problem is in NP-complete if:
the problem is also ...
0
votes
0answers
6 views
Ant Colony Optimization on Maximum Partitioning Graphs with Supply and Demand
I'm still new to the field of Computer Science and I'm having trouble understanding this paper An ant colony optimization algorithm for partitioning graphs with supply and demand. Can I ask for a ...
0
votes
0answers
55 views
Using the proof for NP-hardness for another problem
I already asked similar question here. However, now I restate the question. Let say that $P$ is an NP-hard optimization problem and $Q$ is a problem with unknown complexity. Additionally, we have an ...
0
votes
0answers
17 views
Computing Every Path from a Source to Multiple Destinations [Simpler Algorithm]
How are these two problems different?
I. Find all paths between a source vertex and destination vertex.
II. Find all paths between a source vertex and all vertices in the
graph.
Both of these ...
1
vote
0answers
36 views
What is an example of meta-heuristic algorithm for solving Mario NP-hard problem?
Applying entertainment with computations is my main motivation in studying Computer Science, however, I'm still a neophyte to this field. While searching across the net, I came across this paper ...
0
votes
0answers
15 views
What is the complexity of scheduling jobs vertically and horizontally?
There are $m$ machines, $n$ jobs and $k$ time-slots. For each job $j$ we have $S_j\subseteq\{1,2,\ldots,k\}$. For each machine $i$, job $j$, and time-slot $t$, we have $\gamma_{ijt}>0$.
If job $j$ ...
2
votes
1answer
67 views
A variant of hitting set problem? Is this also a NP-hard problem?
Let's start from finding a minimum hitting set problem. Given a collection of sets $U=\{S_1,S_2,S_3,S_4,S_5,S_6\}=\{\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}\}$, it is ...
0
votes
2answers
72 views
Is P contained in NP-hard?
I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me.
NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained ...
1
vote
1answer
140 views
NP-Complete problem proof
I have an exam in two days and I am not sure if I have understood correctly the way of proving np-completness and how to pick a known np-hard problem to reduce it. Bellow I present a problem which I ...
0
votes
0answers
18 views
Solving the multiple-choice knapsack problem for large input
I need to solve the multiple-choice knapsack problem for a very large input size ($\approx 10,000,000$).
What is best way to practically do this? I've seen some papers describing FPTAS (=Fully ...
2
votes
1answer
84 views
Scheduling to minimize the truncated gaps
I have a single job of unit length, a set of $n$ slots, and a budget of $B$ units. If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled ...
3
votes
0answers
42 views
Scheduling is NP-Hard via vertex cover
Are there any existing proofs involving a reduction of the single machine scheduling problem (in any of its forms really) from vertex cover in order to prove its NP-hardness?
Particularly looking for ...
3
votes
1answer
75 views
Is the knapsack problem NP-hard when $v_i=i$?
The knapsack problem is NP-hard and can be formulated as:
$$\begin{align}&\text{maximize } \sum_{i=1}^n v_i x_i,\tag{P1}\\&
\text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } ...
0
votes
0answers
53 views
Maximum-density multiple-choice knapsack problem
I am looking for work done on solving a problem (specifically I'm looking for an approximation algorithm) which is very similar to a combination of two variations of the knapsack problem: maximum-...
