Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
848
questions
-2
votes
1
answer
19
views
How do you show that Cosmic Kite Problem is NP complete?
A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique.
Cosmic Kite as decision problem
Input: a graph G = (V, E) ...
0
votes
1
answer
43
views
NP-Hard version of TSP if P=NP
If P=NP (polynomial time algorithm for determining whether there exists a route smaller than L) would the NP-Hard version of TSP (finding the minimum distance route) still be NP-Hard? We would only ...
- 1
2
votes
0
answers
27
views
Can a para-NP-Complete problem be $\Sigma^P_2$-Complete in its non-parameterized version?
I have a problem which (I think) have proven to be para-NP-Complete concerning some parameter $k$.
However, I am certainly sure that the non-parameterized version of this problem is $\Sigma^P_2$-...
- 31
2
votes
1
answer
39
views
Finding a Maximum Cut With Force Labeled Vertices for Planar Graphs
The maximum cut problem is a combinatorial optimization problem that seeks to partition the vertices of a graph into two sets, $S$ and $T$, in a way that maximizes the number of edges that cross ...
2
votes
1
answer
94
views
Determining whether two special variants of knapsack have the same optimal value
Given two unbounded knapsack instances, $K_1 = (W_1, weights, values), K_2 = (W_2, weights, values)$, where $W_1 \ne W_2$, what is the complexity of determining $v(K_1) = v(K_2)$ where $v$ returns the ...
- 31
2
votes
2
answers
97
views
No Neighbor Vertex Cover
Let $G=(V,E)$ be an undirected connected graph with a set of vertices $|V|$ and a set of edges $|E|$. A set cover $D$ satisfies $D \subseteq V$ and $uv \in E \implies u \in D \lor v \in D$. A variant ...
1
vote
1
answer
77
views
Constrained Maximum Flow Minimum Cost
Let $G=(V, E)$ be a directed network with a set $V$ of vertices and a set $E$ of edges. Two vertices are distinguished, $s,t$ which are the source and sink respectively. Each edge $(i, j)$ has an ...
1
vote
1
answer
82
views
Is this intersection set problem NP-Hard?
Suppose we have collection of n sets $S_1, S_2, \dots, S_n$. Each set has a size of at least $k$. We know for sure that $\exists k$ sets where all of them contain the same $k$ elements; $|S_1 \cap S_2 ...
- 13
5
votes
1
answer
50
views
NP hardness of adaption of the graph bandwidth problem
Is the following adaptation of the graph bandwidth problem NP hard? If so, which problem could a reduction use?
Given: Graph $G = (V , E ), L:E\to \mathbb N$.
Question: Is there a $f : V \to \mathbb ...
- 51
2
votes
0
answers
54
views
Are there $r$ pairwise edge-disjoint $k$-sets of internally disjoint $s$-$t$-paths? Complexity
Given an undirected graph, two vertices $s$ and $t$, and two integers $k$ and $r$, then a $k$-set of internally disjoint $s$-$t$-paths is defined to be a set of exactly $k$ $s$-$t$-paths that share no ...
- 153
1
vote
1
answer
80
views
NP-hardness of a variation of the bin packing problem
I was wondering if a variation of the bin packing problem where the 'size' of a bin is calculated as the product of item sizes in a bin instead of their sum is NP-hard. It seems like it must be, but I ...
- 13
6
votes
0
answers
168
views
Are there $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are internally disjoint? Complexity
Given an undirected graph, two vertices $s$ and $t$, and two integers $k$,$l$ - what is the complexity of finding $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are pairwise ...
- 153
1
vote
1
answer
71
views
Reduction from dominating set to disconnected dominating set
Consider an undirected graph $G = \langle V, E\rangle$, and a set $S\subseteq V$ of vertices. We say that $S$ is a dominating set, if for every vertex $v\in V$, it holds that $v\in S$, or $v$ has a ...
- 73
1
vote
0
answers
85
views
Complexity of a variant of the Subset Sum Problem (second level polynomial hierarchy)
What is the complexity class of the following variant of the SSP problem:
Input: set of integers $\{x_1,\ldots,x_n\}$, integer $k$ and integer $T$.
Output: Yes, if there exists a subset $S\subseteq \{...
- 31
5
votes
2
answers
348
views
How to find an example for a case in the metric k-center problem
Given $n$ points in a 2d metric space, the $k$-center problem asks us to find a subset of size $k$ of the points which we will call centers. The task is to pick these centers to minimize the maximum ...
- 996
1
vote
1
answer
33
views
Seeking a reference for NP-hardness of optimization problems
Most optimization textbooks do not cover the concept of NP-hardness. Some examples include:
"Convex optimization" by Boyd and Vandenberghe
"Numerical Optimization" by Nocedal and ...
- 821
0
votes
0
answers
63
views
The parameterized complexity of Weighted-CNF-SAT parameterized by the number of clauses
What is the parameterized complexity of Weighted-CNF-SAT, when parameterized by the number of clauses?
Input: A CNF formula $\phi$ with $m$ clauses and $n$ variables, and an integer $k$.
Parameter: $m$...
- 31
1
vote
0
answers
23
views
Approximation Algorithm for Bin packing Variant with Packing Overhead
I recently came up with this bin packing variant and was wondering, if someone has studied it before:
Given: Instance $I$ is a set of tuples $\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$ with $s_{i}, ...
- 11
3
votes
0
answers
81
views
Subset sum problem with big items
Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
- 5,994
1
vote
0
answers
51
views
Complexity of topological sorting with a special restriction
Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types:
Input variable, with in-degree $0$ and out-degree $\geqslant 1$.
A gate, with ...
- 23
1
vote
2
answers
114
views
NP-hardness of modified distance-colouring of graphs
Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
- 11
0
votes
1
answer
32
views
Fully Connected Graph to Lattice
I am looking for algorithms (or at least something similar to the problem definition):
Given a fully-connected weighted graph $G$ with $n$ nodes, find a subset $S$ of edges that form a square lattice ...
- 113
3
votes
1
answer
61
views
What is the complexity of minimising a convex quadratic function over the integers?
The problem of interest is
$$
\min_{x\in\mathbb{Z}^n} \frac{1}{2}x^\top Q x + c^\top x
$$
where $Q$ is a positive definite matrix. I am reasonably sure this can't be solved in poly-time, since the ...
- 133
2
votes
1
answer
58
views
Subset sum reducible to barter economy problem?
I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
1
vote
1
answer
331
views
Finding all stable matchings in stable marriage problem
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
- 11
0
votes
0
answers
17
views
Finding all stable matchings in stable marriage problem [duplicate]
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
- 11
1
vote
1
answer
92
views
Is there an efficient algorithm for this ecommerce optimization problem?
Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules:
There are $n \gt 0$ distinct products in our shopping basket. Each product is ...
- 15
0
votes
1
answer
39
views
Minimizing the number of distinct elements by picking one set from each set of sets
I have a problem as follows. Given a set of sets $U = \{S_1, S_2, … S_N\}$ where $S_i = \{s_1, s_2, ... s_m\}$. Each $s_j \in S_i$ contains a set of distinct elements. I need to pick one $s_j \in S_i$ ...
- 141
1
vote
1
answer
58
views
Is this variant of multiset covering problem NP-hard?
Consider this variant of multiset covering problem.
Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ and $s_k \neq \emptyset$ for all $k$...
- 11
0
votes
1
answer
65
views
Is the flexible bin packing problem NP-complete?
I am currently trying to figure out whether a flavor of the bin packing problem, which I call the "flexible bin packing problem" (F-BPP), is NP-complete.
Here are the definitions for the ...
5
votes
1
answer
1k
views
Can a graph problem remain NP-hard when restricted to cycle graphs?
Does anyone have any examples of NP-hard graph problems which stay NP-hard on cycles, or is this class somehow not able to have NP-hard problems?
I found a similar post concerning trees here which ...
- 807
1
vote
0
answers
34
views
Scheduling jobs with the same release time and different due dates on a single machine
Consider the problem of scheduling jobs with different lengths on a single machine while the jobs have the same release times and different due dates. The goal is to schedule the maximum number of ...
0
votes
1
answer
26
views
Use of the degree variable in an MSOL formula
I am working on giving an MSOL formula for an NP-hard problem; this proves that the problem is linear-time solvable on bounded treewidth graphs. Given a graph $G = (V, E)$, the problem would be to ...
- 162
0
votes
1
answer
51
views
Subexponential reduction
I am working on exact algorithms for an NP-hard problem $P$. I was able to get a $(1.75^n$) time algorithm for split graphs. When it comes to bipartite graphs, the problem becomes hard to tackle. Now, ...
- 162
3
votes
1
answer
108
views
Knapsack with fixed size and flexible profit
We have $3n$ items with profits $p_1, \dots, p_{3n}$ (sum = $P$) and weights $w_1,\dots,w_{3n}$ (sum
= $W$). We want to determine whether we can choose exactly $n$ items with profit at least $P/2 - 1$ ...
- 105
1
vote
1
answer
39
views
Knapsack with fixed size
We have $3n$ items with profits $p_1, \dots, p_{3n}$ (sum = $P$) and weights $w_1,\dots,w_{3n}$ (sum
= $W$). We want to determine whether we can choose exactly $n$ items with profit at least $P/2$ and ...
- 105
0
votes
1
answer
26
views
lower bounds for exact algorithms
I am working on building exact algorithms for NP-hard problems. Let's consider an NP-hard problem $P$. The brute force approach runs in $2^n$ time. In order to prove that there is no $2^{o(n)}$ time ...
- 162
0
votes
0
answers
34
views
How to prove Set-Cover problem is NP hard via reduction from Clique problem?
Since I know that the reduction Clique $\leq_{p}$ Vertex-Cover and Vertex-Cover $\leq_{p}$ Set-Cover are possible, I know how to show this using transitivity property of reductions. However is there ...
- 101
0
votes
0
answers
39
views
List of weakly NP-HARD problems
I need a list of at least 10 weakly NP-HARD problems. I already know the Knapsack problem, partition problem and subset sum problem. Please introduce other weakly NP-hard problems to me.
0
votes
1
answer
35
views
Is minimum interval hitting problem NP-HARD?
Consider this problem:
We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in ...
1
vote
1
answer
63
views
Bipartite matching with constraints on one part
We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
1
vote
0
answers
26
views
What is the name of this extension of the maximum independent set problem?
Problem: we have an undirected graph. Each vertex $v$ has a weight of $w_v$. For each vertex $v$, a nonnegative number $a_v$ is given, and for each edge $e$, a nonnegative number $b_e$ is given. ...
1
vote
0
answers
59
views
What is the name of this matching problem?
We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...
1
vote
1
answer
73
views
Is variable a constant or a parameter
I am working on the $[1,j]$-dominating set problem defined in this paper. In section 4, they study the problem complexity on degenerate graphs and prove that the problem is W[1]-hard for the parameter ...
- 162
0
votes
1
answer
159
views
reduce independent Set into independent Set of distance 4 between all vertices
I want to prove the following problem is NP-complete:
4-Spaced-Set: Assume you have a undirected graph $G=(V,E)$, and a positive integer $k$. Let's say a set of vertices $A \subseteq V$ is $4$-spaced ...
0
votes
1
answer
20
views
NP-HARD optimization problem and instance correlation
If an optimization problem A is NP-hard and P≠NP, then does there exist an instance x of A such that no polynomial algorithm provides an optimal solution for x?
0
votes
1
answer
80
views
On hardness of finding total dominating sets in triangle-free graphs
A total dominating set $S\subset V(G)$ is a set of vertices such that $\forall v\in V(G)$, $v$ has a neighbour in $S$. The minimum total dominating set of $G$ is a total dominating set of $G$ of ...
- 25
2
votes
0
answers
72
views
Fit of two lines to an arbitrary set of points - NP-Hardness
My problem is:
Given $n$ points in $\mathbb{R}^d$, I want to find a partition of these $n$ points into $k=2$ clusters. For each cluster, instead of computing the centroid as in the usual k-means ...
- 43
0
votes
1
answer
322
views
Minimum dominating set on trees
I am working on an NP-Complete problem, i.e., the dominating set. Given a graph $G = (V, E)$, a set $S$ is a dominating set if every vertex $v \in V \setminus S$ has at least one neighbor in $S$. I am ...
- 162
1
vote
1
answer
50
views
What are the necessary requirements for proving NP is closed under complement?
I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why.
$VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\...
- 53