Share Your Experience: Take the 2024 Developer Survey

Questions tagged [np-hard]

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

856 questions
Filter by
Sorted by
Tagged with
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?
39 views

• 131
1 vote
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 ...
• 113
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 ?
1 vote
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 ...
• 367
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 ...
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) ...
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 ...
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$-...
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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
82 views

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 ...
• 153
1 vote
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 ...
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 ...
• 153
1 vote
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 ...
• 73
1 vote
85 views

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 ...
• 6,030
1 vote
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 ...
1 vote
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 ...
• 11
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 ...
• 113
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 ...
• 155
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$ ...
1 vote
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 ...
• 11
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
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 ...
• 15
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$ ...
• 141
1 vote
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$...
• 11
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 ...
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
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 ...
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 ...
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, ...
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$ ...
• 105
1 vote
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 ...
• 105
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 ...
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 ...
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.
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 ...
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$,...