# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

731 questions
Filter by
Sorted by
Tagged with
15k views

### what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSP in the form of VRP ...
628 views

### Recent progress on the next-to-shortest-path problem for directed graphs?

In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem: Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be ...
79 views

### Polynomial time algorihtms for two variants of the decision version of longest walk problem

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm. As I understand it, the longest path problem doesn't allow repetition of edges....
84 views

### strong NP-completeness of multi-dimensional Equal-Subset-Sum

I want to show that the multi-dimensional Equal-Subset-Sum is NP-complete in the strong sense: Given a set of $d$-dimensional vectors of non-negative integers, does there exist two distinct nonempty ...
1 vote
60 views

### Shorter than target vector path algorithm

Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective ...
44 views

### Unbounded Knapsack: Does Increasing capacity increase optimal value?

Our decision problem is as follows: given weights $\mathbf{w}$, values $\mathbf{v}$, and capacities $C_1$ and $C_2$, where $C_1 < C_2$, does the optimal value of unbounded knapsack with the above ...
287 views

### A Travelling Salesman variant where the next distance depends on distance travelled so far

The travelling salesman problem can be seen as a problem of selecting a permutation on $\{1,\ldots,n\}$ of minimun length, where the length of a permutation $\sigma$ is determined by pairwise ...
689 views

### Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Do we know any problem that satisfies the following criteria? It is polynomial-time solvable on trees. It is NP-complete when restricted to graphs of treewidth 2. The problem can be encoded only ...
212 views

2k views

### Is finding Logspace reductions harder than P reductions?

Motivated by Shor's answer related to different notions of NP-completeness, I am looking for a problem that is NP-complete under P reductions but not known to be NP-complete under Logspace reductions (...
1 vote
143 views

### Reordering a DAG with the minimum changes

Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertices in topological order while keeping as many vertices as possible. The problem is: Is it NP-...
321 views

### Is sorting NP-complete?

SORTING problem. Input: A poset which corresponds to a partially sorted list of different numbers. Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array. ...
204 views

### Is Optimal Swap Sorting NP-Hard?

Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to this question, the problem is NP-Complete but the reference given proves NP-Completeness ...
79 views

### On The Complexity of Block-Interchange Distance for Binary Strings

The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable ...
27 views

### Compute a feasible schedule for scheduling on identical parallel machines?

I am considering the offline version of identical parallel machine scheduling with arrival time and deadlines while allowing preemption and no assumption regarding the agreeability of the arrival and ...
88 views

### Complexity of finding a room-partitioning

In a paper by Jack Edmonds and Laura Sanità (link: https://www.sciencedirect.com/science/article/pii/S1571065310001605) the following intriguing result is given: Given a triangulation $T$ of $3n$ ...
75 views

### Set Cover with Multiple covers

I am interested in whether a set cover instance that covers all elements $q$ times may have the property that every sufficiently small subset of this set cover will not cover the elements even once. ...
2k views

### NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
99 views

### maximum independent set in graphs with small number of edges

For the classic maximum independent set problem, a hardness of approximation result of $n^{1-\varepsilon}$ is known by [Hastad, 1996] assuming $\textsf{NP} \not \subseteq \textsf{ZPP}$, where $n$ is ...
147 views

### Is this problem on unambiguous DNFs hard?

Call a DNF formula $\varphi = \bigvee_{i=1}^n C_i$ unambiguous if for every $i\neq j$, $C_i \land C_j$ is unsatisfiable. In other words, the disjunct $C_i$ contains some literal $l$ and $C_j$ contains ...
89 views

### What's the complexity of the "decision version" of counting the paths in a graph?

I learned that "counting the simple paths in a graph(whether directed or not)" is #P-Complete. I'm wondering what the complexity is for its decision version. Here are two types I'm ...
92 views

### Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances

I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances. input and output: input: A satisfiable cnf ...
1 vote
69 views

### Hardness for find the clause for statisfiable 3-SAT problems

The 3-SAT problems are known to be NP-complete so the decision problems are believed to be non efficiently solvable unless P=NP. Yet, there are cases where the satisfiability can be answered such as ...
Problem: Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that ...