Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
21
votes
4answers
829 views

Problems that are counter-intuitively solvable in practice?

Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in ...
21
votes
1answer
864 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 (...
21
votes
2answers
940 views

$NP$-completeness of recognizing the difference of two permutations

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two ...
21
votes
1answer
340 views

Consensus clustering using set union

I've already posted this question a while ago on MathOverflow, but to the best of my knowledge it is still open, so I'm reposting it here in the hope that someone might have heard of it. Problem ...
20
votes
3answers
1k views

Problems that are NP-complete under randomized or P/poly reductions.

In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which ...
20
votes
3answers
1k views

NP complete graph problems about structural properties

(This question is a bit of a "survey".) I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural ...
20
votes
4answers
1k views

Positive topological ordering, take 3

Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix? This question is motivated by this problem: Positive topological ordering ...
20
votes
3answers
644 views

Is it hard to find optimal addition chains?

An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k < i$. The length of the ...
20
votes
1answer
570 views

Minimum chordless odd-cycle graph completion: is it NP-hard?

The following interesting problem came up in my research recently: INSTANCE: Graph $G(V, E)$. SOLUTION: A chordless odd-cycle completion, defined as a superset $E'$ of the edge set $E$ so that ...
19
votes
2answers
949 views

Is feedback vertex set problem is solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set is NP-complete for general graphs. It is known to be NP-complete for degree-8 bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is poly-time ...
19
votes
2answers
1k views

Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

In their paper (p. 503) Garey and Johnson remark: ... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ......
18
votes
5answers
1k views

Why is it important to prove that a problem is NP-complete?

Am I correct in understanding that proving a problem NP complete is a research success? If so why?
18
votes
4answers
1k views

“All-different hypergraph coloring” - known problem?

I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
18
votes
2answers
794 views

Co-NP-completeness of minimal TSP tour?

This problem came out of my recent blog post, suppose you are given a TSP tour, is it co-NP-complete to determine if it is a minimal one? More precisely is the following problem NP-complete: ...
18
votes
2answers
1k views

The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness

The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem. However, in the ...
18
votes
0answers
511 views

Complexity of the densest $k$-subgraph problem on planar graphs

In the densest $k$-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is ...
17
votes
4answers
912 views

Complexity of finding a second solution given a correct solution to an NP-complete problem

I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem. More precisely, ...
17
votes
2answers
2k views

Can strong NP-hardness really be shown using plain polytime reductions?

I recently read a proof that intended to show that a problem was strongly NP-hard, simply by reducing to it (in polynomial time) from a strongly NP-hard problem. This didn’t make any sense to me. I ...
17
votes
1answer
895 views

What is the complexity of this edge coloring problem?

Recently, I have encountered the following variant of edge coloring. Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying ...
17
votes
2answers
627 views

H-free cut problem

Suppose you are given a connected, simple, undirected graph H. The H-free cut problem is defined as follows: Given a simple, undirected graph G, is there a cut (partition of vertices into two ...
17
votes
1answer
1k views

Complexity of interval cover problem

Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to ...
16
votes
4answers
2k views

Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs. I've seen the question regarding the other way around here “Directed” ...
16
votes
2answers
455 views

Is intersection of $k \ge 3$ graphic matroids in P?

It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids. ...
16
votes
1answer
380 views

Natural candidates for the hierarchy inside NPI

Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems ...
16
votes
1answer
1k views

Password hashing using NP complete problems

Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
16
votes
1answer
762 views

What is the complexity of rectangle packing when rotations are allowed?

In the rectangle packing problem, one is given a set of rectangles $\{r_1,\dots,r_n\}$ and bounding rectangle $R$. The task is to find a placement of $r_1,\ldots,r_n$ inside $R$ such that none of ...
16
votes
1answer
706 views

Completeness and Context-Sensitive Languages.

I'm interested in two questions regarding context-sensitive languages (CSL) and completeness: Is there a notion of completeness for CSL, and which languages are complete? Are there natural CSL that ...
16
votes
1answer
411 views

What is the complexity of this graph problem?

Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and the size of $A$ is ...
16
votes
2answers
2k views

Linear diophantine equation in non-negative integers

There's only very little information I can find on the NP-complete problem of solving linear diophantine equation in non-negative integers. That is to say, is there a solution in non-negative $x_1,x_2,...
16
votes
0answers
666 views

Deeper look at Algorithmica?

Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995. He presented five possible worlds we could be living in, depending on how P and NP were related. The ...
16
votes
0answers
359 views

Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?

I am interested in the following problem. Node Multiway Cut on Planar Graphs with terminals on the outer face Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals ...
15
votes
2answers
951 views

NP-hard problems on expander graphs?

In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT? , Nati Linial posed the following open problem: Which $NP$-hard computational problem on graph remain hard when ...
15
votes
3answers
2k views

Complexity of edge coloring in planar graphs

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". What is the complexity of 3-edge coloring of cubic ...
15
votes
1answer
339 views

Two matrices related by a permutation $B = P A P^T$ - complexity

What is computational complexity of the following problem: given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$ If it helps, one ...
15
votes
3answers
3k views

Subset sum vs. Subset product (strong vs. weak NP hardness)

I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard. Subset Sum: Given $X = \{x_1,...,...
15
votes
1answer
911 views

Ranking the Difficulty of NP Hard Problems in Practice

This question is tightly related to another post: Phase Transitions in NP Hard Problems but it is somewhat different. While that question is about the hardness of particular instances of NP hard ...
15
votes
3answers
506 views

Bob's Sale (reordering of pairs with constraints to minimize sum of products)

I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well. Someone has already asked a question related to this problem here - ...
15
votes
1answer
363 views

Hitting set of pairwise intersecting families

A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$. The problem to find a minimum hitting ...
15
votes
1answer
420 views

Validity of exponentiation in a polynomial time reduction

I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer. In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-...
15
votes
1answer
593 views

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ . Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph ...
15
votes
1answer
1k views

Is the following problem NP hard?

Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer. The goal is to find ...
14
votes
5answers
951 views

Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in $S$...
14
votes
1answer
1k views

How can a problem be in NP, be NP-hard and not NP-complete?

For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP. However, in the famous paper "The ellipsoid method and its consequences in ...
14
votes
1answer
405 views

Sampling a uniformly random satisfying assignment

Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists). Clearly ...
14
votes
2answers
1k views

What is the following variation on Set Cover known as?

What is the following variation on set cover known as? Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in ...
14
votes
1answer
437 views

NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is ...
14
votes
1answer
210 views

What is the minimum required depth of reductions for NP-hardness of SAT?

As everyone knows, SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions. It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions. My questions is what is the minimum ...
14
votes
1answer
882 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
14
votes
2answers
527 views

Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

What is the complexity of the following problem? Input: $H$ a Hamiltonian path in $K_n$ $R \subseteq [n]^2$ a subset of pairs of vertices a positive integer $k$ Query: is there a matching $M$ such ...
14
votes
0answers
578 views

Does solving matrix multiplication in quadratic time imply that SETH is false?

I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time. In other words, ...