Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
530
questions
1
vote
2answers
40 views
Is the number of NP-complete problems finite?
It should be straight forward to show that there are infinitely many NP-hard problems:
Proof:
Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and ...
-1
votes
1answer
57 views
Are there any NP-hard problems for which the following statement is true:
$\overline{A} \le A\ and $ $A \le \overline{A}$
Is the following proof correct?
If $\overline{A} \le A \Rightarrow \overline{A} \in NP$ since A is NP-hard $ \Rightarrow A \in coNP$
Since $\...
0
votes
1answer
20 views
NP-Complete reductionTrue/False question explanation
Why is the above statement true? my understanding is:
(1)3SAT reduces to X implies X is NP-complete or harder.
(2)Set Cover reduces to X implies X is neither NP-Complete nor harder.
This ...
1
vote
1answer
55 views
An NP-hard problem reduces to its complement?
I found this statement in a true/false test section:
Could someone explain in laymans why this is a true statement?
My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
0
votes
2answers
131 views
What is wrong with the following $P$ problem?
Our teacher gave us the following statement and we were wondering what is wrong with it.
Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$,
we cannot check ...
1
vote
1answer
2k views
A problem in NP but not NP-complete?
Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
2
votes
0answers
24 views
On the hardness of constraint satisfaction
I am interested in the hardness of the following question.
Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\...
3
votes
1answer
127 views
maximum coverage version of dominating set
The dominating set problem is :
Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ ...
4
votes
1answer
55 views
Partition into paths in a Directed Acyclic Graphs
I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths.
When $b_i=1$ for all the ...
1
vote
0answers
51 views
Optimal ordering - Dynamic programming on subsets
We have a set T of n elements and m subsets $R_i \subset T i = 1,...,m$.
The $S_i$ are not assumed to be different. We also define an ordering of T, a one-to-one mapping $\pi$ of $T$ onto the set of ...
1
vote
1answer
72 views
How to prove Shortest Common Superstring is NP-Hard
After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting ...
-1
votes
1answer
33 views
Another Subset sum problem
Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
4
votes
0answers
38 views
Rectangle Packing with Constraints
I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
1
vote
1answer
53 views
Subset sum to 0/1 knapsack
How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
0
votes
1answer
23 views
How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes
So here's the problem:
-You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid ...
1
vote
1answer
112 views
How do I reduce subset sum to another problem in NP?
I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following.
Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it ...
0
votes
0answers
63 views
Using induction prove that a K-SAT problem is NP-Complete
Using induction on k, how do I prove that the K-SAT problem is NP-complete?
On wikipedia, it describes the Cook-Levin theorem to prove that K-SAT is NPC by reducting the K-SAT problem to a circuit-...
0
votes
1answer
107 views
Reduction from Vertex Cover to Dominating Set
I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles ...
3
votes
1answer
73 views
3-Dimensional Matching with at Most $2n$ Hyperedges
In 3 dimensional matching, we are given a set $M\subseteq X\times Y\times Z$ where $|X|=|Y|=|Z|=n$. A matching in $M$ is a subset $T⊆M$ such that no elements in $T$ agree in any coordinate. The goal ...
1
vote
0answers
57 views
Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem
The unweighted maximum coverage problem is defined as follows:
Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$.
Objective: find a subset $S' \subseteq S$ such ...
4
votes
2answers
58 views
Given a set, partition it into ordered triples
I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$.
The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$?
I was trying to ...
2
votes
1answer
59 views
Partition into pairs with minimum absolute difference, NP-hard?
I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t_1,t_2,\ldots,t_m$ where each $t_i\leq1$ for all $i$.
The question is: can you select $m$ disjoint pairs $(a_i,b_i)$ from ...
7
votes
1answer
68 views
Is 3-colouring NP-hard for 5-colourable graphs?
Recently it was shown that it is NP-hard to find a 5-colouring of a 3-colourable graph.
More generally, it is NP-hard to distinguish $k$-colourable graphs from those that are not $(2k-1)$-colourable, ...
0
votes
1answer
27 views
Grouping n points into groups of size m with objective to have least traveling distance in each group
Assumptions:
There are "n" jobs which are distributed over the city.
Company has "k" available workers.
Each worker can do "x" jobs per day.
"x" is dependent to the worker skills and the distance ...
1
vote
0answers
31 views
Partition a multiset into pairs that sum up to given numbers?
Given a multiset of $2m$ positive numbers, $S=\{s_1,s_2,\ldots,s_{2m}\}$ and given $m$ targets $t_1,t_2,\ldots,t_m$. Can we partition $S$ into $m$ pairs $(a_i,b_i)$ such that $a_i+b_i=t_i$, where $a_i\...
2
votes
2answers
54 views
Clique-or-almost reduction to clique
I saw the posted question here about a direct reduction from near-clique to clique.
Clique-or-almost is like near-clique but with the option for a complete clique of size $k$, I mean that perhaps an ...
5
votes
1answer
81 views
Is GAP NP-hard with at most two balls per bins?
The generalized assignment problem (GAP) [1] is given by:
Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and ...
0
votes
1answer
47 views
Multiple Knapsack Problem with Set of Admissible Balls
We have $m$ bins and $n$ balls.
Each bin $i=1,2,\ldots,m$ can contain at most two balls (not any two balls but two balls from some specific set), see 3.
Each ball $j=1,2,\ldots,n$ can be put into ...
1
vote
1answer
65 views
Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?
Let us say we have $m$ bins and $n$ balls. Every bin $i$ has capacity $c_i$ which is the number of balls that can be put into bin $i$. We have $c_i\geq1$ for all $i$. For each bin $i$, there is a ...
0
votes
0answers
44 views
Which is the most similar NP classic problem, if any exists, to this one?
Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the ...
0
votes
1answer
30 views
Knapsack up to the heaviest item
There are $n$ items with weights $w_1,\ldots,w_n$ and values $v_1,\ldots,v_n$. There is a knapsack with capacity $W$. A subset of items is called feasible up to heaviest item if, once the heaviest ...
4
votes
3answers
254 views
If a problem is not in NP, prove that every NP problem can be efficiently reduced to it
I understand that an NP-hard problem is a problem X such that any problem in NP can be reduced to X in polynomial time.
Does there exist a problem that is hard to solve but problems in NP cannot be ...
2
votes
1answer
68 views
Hitting Set Problem with non-minimal Greedy Algorithm
The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
2
votes
1answer
36 views
complexity of a variant of the subset sum problem
We have a set of positive integers $N=\{a_1,...,a_n\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$.
What is the ...
0
votes
0answers
29 views
What is the name of this problem (the dual of the asymmetric k-center problem)
I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse.
In this ...
2
votes
2answers
121 views
How to prove NP-hardness from scratch?
I am working on a problem of whose complexity is unknown.
By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use.
Finally, I have decided ...
6
votes
2answers
231 views
If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?
Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.
Now I am learning that a convex optimization problem can ...
3
votes
1answer
87 views
Algorithm to find a simple path with maximum weight less than a constant in DAG
Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...
2
votes
1answer
65 views
Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”
In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality.
In Fig. 1.3, the author says a black colored leaf ...
5
votes
0answers
129 views
Is resampling random variables to maximize value NP-hard?
Setup Let $S = {X_1, ..., X_n}$ be a set of independent binary random variable, i.e. $X_i \in \{0, 1\}$, each with prior $P(X_i = 1) = p_i$. The $X_i$ are not iid, so $p_i, p_j$ need not be equal if $...
2
votes
1answer
23 views
How to use c-gap problems to prove inapproximability?
Suppose there is a specific set function with some properties - $f=2^V\to \mathcal{R}$. It is known that the following problem is NP-Hard: Find $S\subseteq V, |S|\leq k$ such that $f(S)$ is maximized....
3
votes
1answer
48 views
Is this variation of set-cover NP-hard to approximate?
The classic set-cover problem is described as follows:
Let $S = \{s_1, ..., s_n\}$ be a target set, and let $\Lambda = \{A_1,
..., A_m: A_i \subset S\}$ be a collection of subsets of $S$. The
...
2
votes
1answer
100 views
If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?
According to this source,
If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to ...
0
votes
3answers
89 views
How Reduction works in proving NP-Hard?
A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq_P X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq_P X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard.
I also ...
2
votes
1answer
101 views
Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G
In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:
Suppose that a friend tells you that a given
graph G is hamiltonian, and then offers to prove it by giving ...
1
vote
1answer
57 views
SImple NP-hard proof question
$3SATplus$
Input: 2 CNF formulas $F_1$, $F_2$ where all clauses have exactly $3$ literals.
Question: Does every truth assignment satisfy at-least as many $F_2$ clauses as $F_1$'s?
Assume ...
1
vote
1answer
28 views
Dubins TSP NP-hardness proof detail
In Le Ny et al.'s paper On the Dubins Traveling Salesman Problem (https://tinyurl.com/y59f7d8x) the authors prove, among other works, that the Dubins Traveling Salesman Problem (DTSP) is NP-hard. I ...
0
votes
1answer
51 views
weighted-clique to vertex cover reduction
WEIGHTED-CLIQUE
input: a undirected graph G that has weighted edges and 2 natural numbers a, b
question: does G have a clique of size a with total weight of b?
I want to prove that this ...
0
votes
0answers
18 views
How to determine the complexity of a mixed strategy NASH equilibrium problem
How to determine a complete-information mixed strategy NASH equilibrium problem with finite numbers of players and strategies? That is, there exists a payoff matrix which shows all the relation among ...
5
votes
1answer
176 views
P vs. NP and Godel's Theorems
This post is based loosely on a previous post, but the presentation is somewhat different and hopefully much more succinct.
Basically, I'm wondering if it is plausible for there to be a formal proof ...
