Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
835
questions
1
vote
0
answers
18
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
73
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,730
0
votes
0
answers
40
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 ...
- 13
1
vote
2
answers
91
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
28
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
54
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
1
vote
1
answer
45
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$ ...
0
votes
0
answers
96
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 ...
- 1
0
votes
0
answers
13
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 ...
- 1
1
vote
1
answer
90
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
32
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
51
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
60
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
977
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 ...
- 737
1
vote
0
answers
30
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
24
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
32
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
107
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$ ...
- 95
1
vote
1
answer
35
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 ...
- 95
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
25
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 ...
0
votes
0
answers
32
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
27
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 ...
0
votes
1
answer
43
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
25
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
57
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
61
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
127
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
77
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
162
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
48
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
2
votes
1
answer
157
views
Partition of two sets for multi-line fitting, NP-hard?
Given two sets of nonnegative numbers $X=\{x_1,...,x_n\}$ and $Y=\{y_1,...,y_n\}$, my problems consists in finding the partition $S \subseteq \{1,...,n\}$ and $\bar{S}=\{1,...,n\}\backslash S$ ...
- 43
0
votes
1
answer
53
views
Max Unique Clique in $\Sigma^2_p$
I want to prove that the language $\text{Max-Unique-Clique} = \{<G> | \text{The maximal clique of $G$ is unique}\}$ is in $\Sigma_2^p$ by using the following $\Sigma_2^p$ machine:
The machine ...
- 100
1
vote
0
answers
18
views
How difficult are lattice algorithms for low-dimensional lattices?
Most lattice problems, such as the shortest vector problem, the closest vector problem, shortest basis problem, etc, are NP-hard and thus conjectured to be worst-case exponential time in the rank of ...
- 837
2
votes
1
answer
119
views
Budgeted Independent Vertex Cover
Suppose that we are given a graph $G = (V,E)$ and a number $n$. The problem is to find an independent set $I$ with $|I| = n$, such that number of vertices covered by $I$ is maximized (that is, the ...
- 131
1
vote
1
answer
253
views
NP-completeness of problem based on non-arbitrary instance
To prove that a problem is NP-complete, one has to show that it is both (a) in NP and that it is (b) NP-hard by reducing a known NP-complete problem to it in polynomial time.
Regarding the reduction, ...
- 113
2
votes
1
answer
67
views
Selecting a submatrix of a binary matrix NP hard?
I have the following problem and I am wondering if it is NP Hard or not.
Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$.
A ...
- 23
1
vote
1
answer
54
views
How can we find a shortest closed walk passing through all vertices?
How can we find a walk with the minimal length starting from a vertex $v$, passing through all vertices and returning back to $v$?
We allow vertices and edges to be repeated along the walk. The ...
- 303
0
votes
0
answers
43
views
Hardness of the bin packing problem
I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that
$$
1 > a_1 \geq a_2 \geq \dots \geq a_n > 0
$$
The ...
0
votes
0
answers
20
views
Solving a weighted minimum dominating set problem with its unweighted counterpart?
Question
Is it possible to find a solution to the weighted minimum dominating set problem, by solving a (related), unweighted minimum dominating set?
Elaboration
In essence, can one convert a ...
- 123
2
votes
2
answers
609
views
Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?
You are given $n$ lists. The $i$-th list contains $k_i$ subsets of $\{1, \ldots, m\}$. You are also given an integer $s$. You should decide whether it's possible to pick up exactly one element (that ...
2
votes
1
answer
104
views
Is the following binary quadratic integer programming NP-Hard？
I'am trying to prove the following binary quadratic integer programming problem NP hard.
$$
\min \frac{\sum\limits_{i=1}^m(u_i-\bar u)^2}{m}\text{ , where }u=Q x,Q\in\mathbb{R}^{m\times n}\\
s.t. \...
- 23
0
votes
0
answers
67
views
Finding a Polynomial Time algorithm for the 3-SAT Problem
Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause :
Ai = (xr $\lor$ xs $\lor$ xt)
where 1 $\le$ r,s,t $\le$n and ...
0
votes
0
answers
40
views
Envy-Free Allocation is NP-Hard
If we consider the class fair division problem where we have a set of $n$-agents and a set $M$ of $m$-items, where each agent has a valuation function defined on the set of items $$v_i : 2^m \...
- 31
0
votes
1
answer
85
views
Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier
For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X
a1x1 + a2x2 + ... + ...
0
votes
1
answer
122
views
System of equalities and inequalities is NP-hard using a reduction from 3COLORING
We are require to show that a problem where the input is a system of equalities and inequalities, each involving polynomials of degree at most 2 (with integer coefficients) in n real variables x1, x2,...
- 25
1
vote
1
answer
44
views
Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions
Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that ...
4
votes
2
answers
102
views
Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)
Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true?
$A \leq_m$ B
$B \leq_m$ A
In other words, is there always a relationship between any two arbitrary NP-hard ...
- 327