Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
435 questions
2
votes
1answer
26 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
62 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 .
1
vote
0answers
20 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
17 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 ...
0
votes
2answers
84 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
22 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/...
0
votes
1answer
39 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
28 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
0answers
13 views
Regex engine: A polynomial algorithm for backreferences?
During my search for a way to integrate efficiently backreferences (using backtracking) into a text-directed regex engine, I found a paper entitled Extending finite automata to efficiently match Perl-...
0
votes
1answer
60 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
52 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
30 views
Variant of an approximation algorithm for vertex cover
Here is an approximation algorithm that finds vertex cover of a graph.
...
0
votes
1answer
106 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
59 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
83 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
59 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
32 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
473 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
50 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
58 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
46 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
41 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
38 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
66 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
38 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
32 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, ...
0
votes
1answer
35 views
Karp hardness of an equidistant set in digraph
Following the success of the undirected version:
Karp hardness of an equidistant vertex set
Inspired by the success of this long ago question:
NP-hardness of problem with indices and subsets
We ...
1
vote
0answers
44 views
Karp hardness of a simply equidistant vertex set
Following the success of the previous question:
Karp hardness of an equidistant vertex set
I continue to propse yet another computational problem. This time, we modify the notion of an equidistant ...
2
votes
1answer
63 views
Karp hardness of an equidistant vertex set
What is the hardness of the following problem?
Input: An undirected graph $G(V, E)$ and a natural number $k$
Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO
$\...
1
vote
1answer
26 views
Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?
Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^...
4
votes
0answers
28 views
Finding the “most modular” subset of graph vertices, i.e. that minimize disagreement inside and outside
Let $G = (V, E)$ be a graph. I want to find the subset of vertices of $G$ that minimizes a certain modularity cost. In our setting, the modularity cost of a subset $X$ is defined as the number of ...
0
votes
0answers
27 views
Edge-midpoints cover with radius 1
This is in a series of posts. Previous quetion:
Vertex cover with covering radius 2
Other series: Karp hardness of searching for a matching split
In this problem, our cover for a given undirected ...
4
votes
1answer
50 views
Vertex cover with covering radius 2
Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices?
A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
3
votes
1answer
67 views
Karp hardness of searching for a matching split
UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
1
vote
1answer
69 views
Maximum induced tree
Given an undirected graph $G(V, E)$, how hard is it to decide whether it has an induced tree consisting of $k$ vertices, where $k$ is also given in the input?
3
votes
1answer
36 views
Karp hardness of searching for a matching erosion
First, read the previous question: Karp hardness of searching for a matching cut
As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
1
vote
3answers
79 views
Defining a graph decision problem not in NP
I have been doing some research online looking for graph problems that are decidable but not in NP. I have found the concept of succinct graphs, which if I understand properly, consist of making the ...
4
votes
2answers
87 views
Karp hardness of searching for a matching cut
Follow-up question in the series:
Karp hardness of searching for a matching erosion
Karp hardness of searching for a matching split
Maximum Matching Cut problem
Input: An undirected graph $G(...
1
vote
1answer
23 views
Hardness of $2$ edge-disjoint spanning trees decomposition
The question is clear from the title. What is the complexity of the following decision problem:
Input: An undirected graph $G(V, E)$
Output: $\mathrm{YES}$ if $G$ can be decomposed into two ...
-3
votes
2answers
161 views
Does deep learning infer P = NP?
The question comes from the following scenario,
assume we have the traveler problem which is NP (the one where a traveler wants to visit all countries with the lowest cost(by summing up all flights))
...
0
votes
3answers
28 views
Collection of meta-reductions in theory of $\mathrm{NP}$-completeness
I want to start a wiki post about meta-result of meta-reductions in the theory of $\mathrm{NP}$-completeness.
This can be regarded as a reference request post. Any links are appreciated.
At least, ...
