Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [np-hard]

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

Filter by
Sorted by
Tagged with
-1 votes
1 answer
27 views

Acceptance of Turing Machines is NP-Hard?

I had a question in my exam 'Show that the acceptance of turing machines is NP-Hard'. How do I go about this question?
josh hackentoff's user avatar
3 votes
1 answer
39 views

Harder version of the k-partition problem

Given a sequence $q_1, \ldots, q_n$ of numbers, decide if the set $I=\{1,\ldots,n\}$ can be partitioned into $k$ sets $I_1, \ldots, I_k$ such that $\sum_{i\in I_1} q_i=\sum_{i\in I_2} q_i = \dots = \...
Lisa Ellingwood's user avatar
2 votes
2 answers
40 views

Least interrupted max flow after removing K edges algorithm

Given a graph $G=(V,E)$ and $k < |E|$, identify $E' \subset E$ such that $|E'| = k$, so that the max flow in the graph $(V, E')$ is as large as possible. Is this possible in polynomial time? Is any ...
Sriram's user avatar
  • 155
0 votes
1 answer
30 views

Robust maximum weight forests with weights on edges

In an undirected weighted graph with edge weights, the task is to find a spanning tree T. An adversary will delete two edges (not necessarily from T), and subsequently, we can add an edge (excluding ...
Toyllo's user avatar
  • 1
1 vote
0 answers
28 views

NP-hardness of subset sum of multiple supersets

Given the following problem: Input: A set of disjoint sets $s_1, s_2, \dots s_n$, and an integer $K$ Question: Is there a set A with $|A|= n$ and $|s_i \cap A| = 1$ for all i from 1 to n, s.t. $\sum_{...
SimonNW's user avatar
  • 131
1 vote
1 answer
45 views

Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
Lebecca's user avatar
  • 113
-1 votes
1 answer
26 views

Show that it is Np-hard to determine whether a given graph has the crossing number k

I want to prove that this problem to find whether the crossing number of any given graph is K or not, is NP-Hard. I don't know how to do this. Can someone help me with this ?
Virar's user avatar
  • 1
1 vote
1 answer
44 views

Deciding if a regular language is empty can be done in polytime but deciding if it does not accept {0,1}* is not?

In my class we have discussed the fact that, given a representation $\langle R\rangle$ of a regular expression $R$, we can decide whether it accepts any string by first finding an equivalent NFA, and ...
Addem's user avatar
  • 367
0 votes
1 answer
20 views

NP-hardness of optimization with promise

Consider the Minimum Bisection problem, which asks, for a given $k$, whether the vertices of a graph can be partitioned into two parts of equal size such that the number of edges between these two ...
user166511's user avatar
-2 votes
1 answer
27 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) ...
Nicolò Bonacorsi's user avatar
0 votes
1 answer
46 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 ...
David's user avatar
  • 3
2 votes
0 answers
29 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$-...
user3445340's user avatar
2 votes
1 answer
42 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 ...
Daniel García's user avatar
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 ...
rossignol's user avatar
2 votes
2 answers
102 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 ...
Daniel García's user avatar
1 vote
1 answer
80 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 ...
Daniel García's user avatar
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 ...
Xfae's user avatar
  • 13
5 votes
1 answer
55 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 )$ with $L\colon E\to \mathbb N$. Question: Is there a $f\...
CubeArrow's user avatar
2 votes
0 answers
57 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 ...
tgnome's user avatar
  • 153
1 vote
1 answer
81 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 ...
Sharp Edged's user avatar
6 votes
0 answers
170 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 ...
tgnome's user avatar
  • 153
1 vote
1 answer
74 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 ...
Zumikya's user avatar
  • 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 \{...
user3445340's user avatar
5 votes
2 answers
352 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 ...
Simd's user avatar
  • 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 ...
Fraïssé's user avatar
  • 821
0 votes
0 answers
75 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$...
user3445340's user avatar
1 vote
0 answers
24 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
82 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
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 ...
user779130's user avatar
1 vote
2 answers
116 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
34 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
65 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
  • 155
2 votes
1 answer
61 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
1 vote
1 answer
383 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
  • 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 ...
void's user avatar
  • 11
1 vote
1 answer
93 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
43 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
61 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
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 ...
thunderbird30's user avatar
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 ...
J. Schmidt's user avatar
1 vote
0 answers
35 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
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 ...
Balchandar Reddy's user avatar
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, ...
Balchandar Reddy's user avatar
3 votes
1 answer
109 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
  • 105
1 vote
1 answer
41 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
  • 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 ...
Balchandar Reddy's user avatar
0 votes
0 answers
39 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
41 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
36 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
1 vote
1 answer
76 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
2 3 4 5
18