Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
10
votes
2answers
577 views

Exact exponential-time algorithms for 0-1 programming

Are there known algorithms for the following problem that beat the naive algorithm? Input: A system $Ax \le b$ of $m$ linear inequalities. Output: A feasible solution $x^*\in \{0,1 \}^n$ if ...
7
votes
5answers
1k views

Multidimensional knapsack STRONGLY NP-complete

Who can point me to a reference where it is actually shown that multidimensional knapsack is strongly NP-complete? I have found loads of papers where they claim it is, without citation; I have found ...
7
votes
2answers
364 views

Complexity of a variant of the max word problem. NP-complete?

I'd like to be able to state that the following problem is NP hard. I am wondering whether anybody have any pointers to related/recent work? The problem: Given a finite set of transition matrices $A$ ...
7
votes
2answers
424 views

Binary matrix column subset selection complexity

Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no ...
7
votes
3answers
854 views

Non-rooted MST of directed graph

I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the ...
5
votes
1answer
708 views

Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in ...
4
votes
1answer
158 views

Max Sum Product Multi-objective Shortest path problem

Is anything known about the following problem: I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1. A path is first assigned a vector, ...
3
votes
1answer
94 views

how to achieve a topological sort of an given sequence with minimum swaps

For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum ...
3
votes
2answers
334 views

Complexity of the Hamiltonian Subcycle problem

The problem is as follows: Given a graph $G$, find a (vertex) disjoint set of cycles $C$ on $G$ such that every vertex is visited by a cycle exactly once. My question is then: what is the ...
3
votes
1answer
2k views

The significance of NP-Hard Problems in Cryptography

I didn't refer any literature but thought this was ideal to get views from people here.. Assuming that P=NP is proved would cryptography(only provable security) be impossible? Since the adversary can ...
2
votes
2answers
352 views

For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist $k$-...
2
votes
1answer
74 views

Constant Width Max Sum Product Multi-objective Shortest path problem

This question is a follow-up on the question I asked three days ago here. For convenience I restate it here. I am given a graph. Each edge is labelled by a vector of numbers, called weights. They ...