Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
-3
votes
0answers
37 views
Does P=NP? (The big question) [closed]
If you know much about theoretical computer science, you have heard the question before.
This site has plenty of questions posted about the implications of one answer or another to this question (...
2
votes
1answer
42 views
How to partition a set in order to minimize the number of the elements and their interactions?
Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From ...
3
votes
0answers
73 views
A special case of the SUBSET SUM problem
Consider the following special case of SUBSET SUM
Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary.
Encoding: These inputs (...
1
vote
0answers
21 views
Given a subset of numbers $1, \dots, n$, find the minimal subset of numbers $1, \dots, n$ sums of every subset of which cover all sums of first subset
Given a subset $A = \{a_1, a_2, \dots, a_k\}$ of numbers $\{1, 2, \dots, n\}$, find another subset $B = \{b_1, b_2, \dots, b_t\}$ of numbers $\{1, 2, \dots, n\}$ of minimal size (that is, minimise $t$)...
2
votes
1answer
49 views
Reducing the vertex cover problem to a variation of the vertex cover problem [duplicate]
The following variation on the vertex cover problem was given:
Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$?
I was asked to prove that ...
1
vote
1answer
52 views
Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?
Is the following true or false? Why?
Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.
2
votes
1answer
41 views
Reducing 3SAT to a Set Splitting Problem
I want to be able to reduce the 3SAT problem to a flavor of set-splitting problem. Basically, given $n$ items and $m$ subsets $S_1, S_2,...,S_m$ of these items I want a yes or no answer based upon the ...
3
votes
1answer
35 views
How to generate snowflakes of a fixed area as challenges for the FridgeIQ puzzle?
I have been presented a set of FridgeIQ by a friend and she has planted an idea in my head.
FridgeIQ is a geometric disection puzzle consisting of 16 polygonal tiles as seen in the terrible picture ...
2
votes
2answers
137 views
Negative simple path NP-Complete
Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$
My approach was to ...
0
votes
1answer
30 views
Is this problem hard? Finding all the subsets of size k from a sequence of n numbers
I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of ...
0
votes
1answer
70 views
Showing party invitation problem is np-complete
Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like ...
1
vote
1answer
46 views
Show Resource Allocation Problem is NP-Complete
We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...
1
vote
1answer
35 views
Finding a suitable NP-complete problem for reduction
We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a ...
1
vote
1answer
31 views
Why Cook-Levin thorem's proof can mean SAT's NP-Hardness
I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ ...
0
votes
0answers
36 views
Why finding out an independent set of size k is in NP-C and not in P? [duplicate]
I came across a statement in my book which claims that the problem P1 in NP-C and P2 is P.
P1: Given graph G(V, E), find out whether there exists an independent set of size k in the graph, where k is ...
1
vote
2answers
30 views
NP-hardness does not imply lower bound, strictly speaking?
A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.
Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
3
votes
1answer
41 views
Proving NP hardness about graph creation problem with triangle number
I have graph creation problem.
Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
2
votes
1answer
71 views
Max flow and Matching problem
Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .
2
votes
0answers
23 views
Karp hardness of two vertex sets in a digraph
Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that:
$|S|+|T|=k$
For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming ...
0
votes
0answers
21 views
Finding if a given problem is a Np-Hard problem - recruitment problem
I have to prove that the following Recruiting problem a NPC-problem.
Input: n candidates and m positions and a matrix A $\in {Q^{n\times n}}$. Each entry $A_{ij}$ with i < j tells how much gets ...
1
vote
2answers
98 views
How to generate an instance for an NP_hard proof, where each element has two inputs?
I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
1
vote
0answers
24 views
Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles
Given a 4-regular graph, is it NP-complete to test whether it can be decomposed into two edge-disjoint Hamiltonian cycles?
0
votes
1answer
33 views
Graph Edit Distance
Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance,
Advances in Computer Vision and Pattern Recognition.
Link: https://www.springer.com/cda/content/document/...
1
vote
1answer
64 views
Reducing subset sum to even subset sum
I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even ...
0
votes
1answer
30 views
Karp reduction from NP-hard problem to unknown problem
If I know that problem $A$ is NP-hard, but know nothing of problem $B$ and I know that the following Karp reduction is true:
$$A \to B \, .$$
Is it correct to conclude that $B$ must also be NP-hard?
6
votes
2answers
1k views
Relation between Undecidable problems and NP-Hard
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
...
0
votes
1answer
63 views
Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one
What is the complexity of this problem
EULERIAN ARC REVERSAL
Input: a directed graph $G(V,A)$ and an integer $k$
Output: YES if $k$ arc reversals are enough to transform $G$ into an ...
1
vote
0answers
20 views
Proof that MAX-2-SAT is NP-hard [duplicate]
According to Wikipedia, while the 2SAT problem is polynomial, its maximization variant MAX2SAT is NP-hard. But, they do not provide a reference for this claim. Is this obvious? If not, where can I ...
2
votes
1answer
24 views
NP-Hard on Complete Graphs
I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a ...
1
vote
1answer
158 views
Gerrymandering Problem: Variant on Set Partitioning
I was recently helping a friend with homework from a dynamic programming class, and this was the question:
Given a set of
n
precincts
P1
,...
Pn
, each containing
m
votes, with <...
1
vote
1answer
34 views
Variant of an approximation algorithm for vertex cover
Here is an approximation algorithm that finds vertex cover of a graph.
...
0
votes
1answer
147 views
How can I show that a problem is not $NP$
Consider the following image:
The problem is: can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up? Prove that this problem is $NP-Hard$.
I ...
0
votes
1answer
65 views
Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph
Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+...
1
vote
2answers
87 views
If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?
I came across this question while studying for an exam:
T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ ...
1
vote
1answer
25 views
Complexity of two cycles which differ by $1$ in length
Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length.
What is the complexity of this problem?
2
votes
1answer
60 views
Is SAT known to be non-context-free or even non-regular?
We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas.
Has something similar been done for SAT?
2
votes
1answer
34 views
Computational complexity of maximizing sum of rational functions
I have a optimization problem:
$$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
2
votes
3answers
601 views
What will happen to NP-Hard problems if P=NP
I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.
He further said that if we can ...
1
vote
1answer
51 views
Karp hardness of directed monochromatic triangle problem
Monochromatic problem is a classic NP-complete problem.
Does the complexity stay NP-complete if we use directed graph?
DIRECTED MONOCHROMATIC TRIANGLE problem:
Input: A digraph $G(V,A)$
...
1
vote
1answer
60 views
Is this an $NP$-complete problem: Product-2-Partition
I want to prove the NP-hardness of my problem P in scheduling. I was trying with Partition, 3-Partition and Subset product, But neither was successful.
Now, I can reduce a problem, say PRODUCT-2-...
0
votes
0answers
10 views
Karp hardness of a supportive clique in digraphs
In a directed graph (digraph) $G(V,A)$, a set of vertices $C\subseteq V$ is called a supportive clique if (1) for every $u\neq v$ in $C$, either $(u,v)\in A$ or $(v,u)\in A$ and (2) for every $u\in C$,...
0
votes
1answer
21 views
Karp hardness of a diameter-decreasing planted clique
A diameter-decreasing planted clique in an undirected graph $G(V,E)$ is a set of vertices $\mathcal{C}\subseteq V$ such that if we add all the missing edges between any pair of vertices in $\mathcal{C}...
1
vote
1answer
47 views
For each given set choosing either it or its complement such that their union exactly has a given size
Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}...
0
votes
1answer
48 views
Karp hardness of a clique with given number of outer-incident edges
A clique in an undirected graph $G(V,E)$ is a subset of vertices $\mathcal{C}\subseteq V$ every pair of which is adjacent $u,v\in \mathcal{C}\implies uv\in E(G)$.
Given a clique $\mathcal{C}\subseteq ...
3
votes
0answers
42 views
Karp hardness of a module in a graph
DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property:
For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
0
votes
1answer
41 views
On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem
in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it.
Besides, it's easy to ...
1
vote
2answers
68 views
Karp hardness of testing for homomorphisms to a fixed non-bipartite graph
Description: Suppose that we are given a fixed non-bipartite graph $H$. A graph $G$ is loopless surjectively homomorphic to $H$ if there exists a loopless surjective homomorphism $\varphi:V(G)\to V(H)$...
1
vote
1answer
39 views
Karp hardness of a vector system allocation
Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies ...
1
vote
1answer
33 views
Karp hardness of a guarding set in digraph
Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following.
A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set ...
1
vote
2answers
48 views
Karp hardness of digraph coloring without monochromatic dicycle
Problem statement:
Input: a digraph $G(V, A)$ and a natural number $k$
Output: YES if it is possible to color all vertices of $V(G)$ by $k$ colors such that no directed cycle is monochromatic, ...
