Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
581
questions
0
votes
0answers
37 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
64 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
116 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
58 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
242 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
175 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
0answers
30 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 is the realization problem.
I have looked up several references [2][3][4]. None of the ...
0
votes
0answers
44 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
64 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
55 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
64 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
141 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
85 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
53 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
47 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
27 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
51 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
137 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
217 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
12 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
38 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
16 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
14 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
52 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
66 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
17 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 ...
1
vote
1answer
73 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
41 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
72 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
39 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-...
1
vote
0answers
36 views
Minimun k-union from a different angle
I'm looking for work done on solving some problem which is very similar to the minimum k-union.
The problem:
There's a set of elements $E=\{e_1,e_2,...,e_k\}$ of size $k$, and a family of sets $S_1,...
1
vote
1answer
36 views
Minimize the sum of gaps
I have a set of $n$ objects $\{1,2,\ldots,n\}$ where object $i$ has weight $w(i)$ and we have a capacity $W$. I would like to pick a subset $S=\{a_1,\ldots,a_m\}\subseteq \{1,2,\ldots,n\}$ of the ...
2
votes
1answer
33 views
Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?
Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following:...
1
vote
1answer
75 views
Prove a TM problem is NP-complete
Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$
This question looks weird to me ...
4
votes
1answer
146 views
Algorithm to create dense style crossword puzzles
I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of ...
1
vote
0answers
97 views
Prove Product Partition is NP-complete in the strong sense
I am trying to understand how to prove that the Product Partition problem is NP-complete in the strong sense. The problem is similar to the normal Partition problem, except in this case the product of ...
0
votes
0answers
42 views
What is at least weakly NP-hard problem?
It is known that some problem P is at least weakly NP-hard. What does at least part of the statement mean? Is it possible that problem P is strongly NP-hard? Is this a stronger, i.e. more precise, ...
0
votes
2answers
68 views
How is the Longest Path Problem NP complete?
From the following link:
https://www.csie.ntu.edu.tw/~lyuu/complexity/2016/20161129s.pdf
So basically, in our iff proof, we have to show two directions:
Forward: If Hamiltonian Path has a yes-...
1
vote
1answer
31 views
Color coding to get an FPT algoirthm for $k$ disjoint triangles
Consider the following problem:
Input: A graph $G=(V,E)$ and an integer $k \in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?
Assume we want to use color coding to develop an FPT ...
0
votes
0answers
29 views
K-Uniform Hypergraph Strong Coloring
I want to ask if strong coloring of a k-uniform hypergraph using only k colors is NP-Hard or NP-Complete? If you can add a reference this will be helpful.
1
vote
5answers
155 views
NP-hard or not: partition with irrational input or parameter
See some related questions in Cont: NP-hard or not: partition with irrational input or parameter
Given a set $N=\{a_1,...,a_{n}\}$ with $n$ positive numbers and $\sum_i a_i=1$, find a subset $S\...
0
votes
0answers
50 views
NP-hard or not: partition with finite irrational input [duplicate]
Original Problem
Given a set $N=\{a_1,...,a_{n}\}$ with $n$ positive numbers and $\sum_i a_i=1$, find a subset whose sum is $x_*$, where $x_*$ is a known fixed irrational number and $x_*\approx 0.52$....
2
votes
1answer
151 views
Hardness of a scheduling/assignment problem
I am trying to prove the hardness of the following problem. This problem is from google hashcode, qualification-round, 2020.
Hier is a brief description of the problem. Given a list or libraries and ...
1
vote
1answer
140 views
Connection between vertex cover and P=NP
I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it.
In an undirected graph $G(V,E)$, ...
