Questions tagged [np-hard]

decision problems that are at least as hard as NP-complete problems

Filter by
Sorted by
Tagged with
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}, ...
blackdra_gon's user avatar
3 votes
0 answers
71 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 ...
Erel Segal-Halevi's user avatar
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 ...
user779130's user avatar
1 vote
2 answers
90 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 ...
r236's user avatar
  • 11
0 votes
1 answer
25 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 ...
EnderNicky's user avatar
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 ...
Sriram's user avatar
  • 133
1 vote
1 answer
38 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$ ...
redbull_nowings's user avatar
0 votes
0 answers
93 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 ...
void's user avatar
  • 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 ...
void's user avatar
  • 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 ...
Jo Ma's user avatar
  • 15
0 votes
1 answer
27 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$ ...
calveeen's user avatar
  • 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$...
Josh's user avatar
  • 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 ...
thunderbird30's user avatar
5 votes
1 answer
975 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 ...
J. Schmidt's user avatar
1 vote
0 answers
29 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 ...
Soroush Vahidi's user avatar
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 ...
Balchandar Reddy's user avatar
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, ...
Balchandar Reddy's user avatar
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$ ...
user57012's user avatar
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 ...
user57012's user avatar
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 ...
Balchandar Reddy's user avatar
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 ...
Yavuz Bozkurt's user avatar
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.
Soroush Vahidi's user avatar
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 ...
Soroush Vahidi's user avatar
0 votes
1 answer
42 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$,...
Soroush Vahidi's user avatar
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. ...
Soroush Vahidi's user avatar
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 ...
Soroush Vahidi's user avatar
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 ...
Balchandar Reddy's user avatar
0 votes
1 answer
124 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 ...
andydandy 's user avatar
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?
PatrickBateman's user avatar
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 ...
Ankit Gayen's user avatar
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 ...
T. Pmp's user avatar
  • 43
0 votes
1 answer
161 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 ...
Balchandar Reddy's user avatar
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\...
Skynet's user avatar
  • 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$ ...
T. Pmp's user avatar
  • 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 ...
OriFrid's user avatar
  • 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 ...
Mike Battaglia's user avatar
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 ...
matheg's user avatar
  • 131
1 vote
1 answer
251 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, ...
pcko1's user avatar
  • 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 ...
D. Sena's user avatar
  • 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 ...
licheng's user avatar
  • 303
0 votes
0 answers
41 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 ...
TheCollegeStudent's user avatar
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 ...
a.t.'s user avatar
  • 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 ...
Vladislav Bezhentsev's user avatar
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. \...
OvinaSun's user avatar
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 ...
Pathlessbark8's user avatar
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 \...
Doc Stories's user avatar
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 + ... + ...
automatically's user avatar
0 votes
1 answer
120 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,...
staz6's user avatar
  • 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 ...
Benedict Bien's user avatar
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 ...
Andrew Baker's user avatar

1
2 3 4 5
17