# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

566 questions
Filter by
Sorted by
Tagged with
61 views

### How to make any graph 2-degenerate?

I have to show a PPT(polynomial time reduction) from 'Colorful graph Motif' to '2-Degenerate Steiner Tree'. As input graph should be 2-degenerate, but here is normal graph G (that is, basically an ...
307 views

### What is the simplest known solver for a np-complete problem?

Lets define the simpler of two terms as the one with shortest description length on the untyped λ-calculus. Trying to find the simplest solver for a np-complete problem, I've got this: ...
139 views

### NP Hardness of Metric Steiner Tree

It is known that the metric steiner tree problem is NP hard (Garry and Johnson ). I wanted to know if there is a simpler way of proving the same. Specifically, I am trying to find a polynomial ...
116 views

### Difference between 'Reductions' in algebraic problems vs “Reductions” in Computational Intractability [closed]

When I read NP-completeness for the first time, I really wondered why is the concept of Reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special ...
313 views

### What is meant by “if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP”?

For example, for the $k$-center problem we want to prove that a 2-approximation algorithm is optimal. A proof is presented on page 39 (Theorem 2.4) in Williamson and Shmoys, The Design of ...
175 views

88 views

### Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. (notice how many times the 2 is touched [circled in red ...
440 views

### Proving NP-hardness of scheduling problem (total weighted completion time)

Consider the problem $P \mid \mid \sum w_j C_j$. I want to prove that this problem is (strongly) NP-hard by reducing from $3$-Partition, but I am not really sure how to do this. Just to be precise, ...
560 views

### Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
2k views

### Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
### open problems on $NP$-complete? [closed]
How can we find the list of open problems on $NP$-comlpete?