Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
5
votes
3answers
247 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.
...
-3
votes
0answers
28 views
reduction from dominating set to dominating value [closed]
Give a reduction from dominating set (DomSet) to dominating value (DomVal):
DomVal = {(G,p)| G is an undirected graph with V’⊆V and val_G(V’)≥p}
where val_G is the number of dominated vertices not in ...
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
57 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 ...
0
votes
0answers
38 views
NP-hardness proof for a cut problem on weighted directed graphs
I should create a polynomial-time decision algorithm or prove that the following problem is in NP:
Input: $G=(V,E)$ a complete directed graph with $n$ nodes and $n(n-1)$ edges. For each node $v$ ...
0
votes
0answers
32 views
NP-hardness for a binary stochastic quadratic programming
I have the following optimization problem:
$$\min_{\mathbf{x}} \; \mathbf{x}^T\mathbf{P}(\mathbf{x}) \mathbf{x} \\ \text{s.t.} \; ||\mathbf{x}||_1 = K$$
where $\mathbf{x} \in \{0, 1\}^N$ is a binary ...
1
vote
0answers
19 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
49 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
28 views
Variant of an approximation algorithm for vertex cover
Here is an approximation algorithm that finds vertex cover of a graph.
...
0
votes
1answer
78 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
56 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^+...
0
votes
0answers
25 views
How to prove that this TSP variation is NP-Hard?
The problem is as follows: given a list of cities, a list of distances between them, and upper bounds for date/times that the cities must have been visited by, compute the shortest (optimal) going ...
1
vote
2answers
82 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
58 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
30 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
406 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
44 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
34 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
44 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
40 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
35 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
25 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^...
0
votes
0answers
65 views
Is the following problem generalizing X3C?
The first problem is X3C for which I try to find out whether it's a special case of the second problem.
The second one is a stacking problem for which we have an itemset $I := \{i_1, ..., i_n\}$, $m$ ...
4
votes
0answers
27 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
35 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
77 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
22 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
139 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
27 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, ...
0
votes
1answer
28 views
Cook completeness of a variant of Vertex Cover
Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$?
Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$
Output: YES if there exists a vertex cover $C'\...
4
votes
1answer
58 views
Ordered set cover problem: is it NP-hard?
Given a set of elements $U=\{1,2,\ldots,n\}$ and a collection of $m$ sets $\{S_1,S_2,\ldots,S_m\}$ whose union equals $U$. Each element $e$ of a set $S_i$ has a weight $w_i(e)$. The weight $w(S_i)$ of ...
2
votes
2answers
119 views
Is this problem NP-hard? Maximizing selected sets so that their union is less than k?
There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union.
I'm currently ...
1
vote
1answer
27 views
Optimal combination, given pairwise costs
I want to pick k objects from a pool of n. Not any k objects, the optimal k objects: that which minimizes the cost of the set, defined as the sum of pairwise costs for all pairs within the set.
What ...
