Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
-1
votes
1answer
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 ...
-1
votes
1answer
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: ...
-1
votes
1answer
139 views

NP Hardness of Metric Steiner Tree

It is known that the metric steiner tree problem is NP hard (Garry and Johnson [1977]). I wanted to know if there is a simpler way of proving the same. Specifically, I am trying to find a polynomial ...
-3
votes
1answer
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 ...
-3
votes
1answer
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 ...
-3
votes
1answer
175 views

Can we map this problem to subset-sum?

Let there be $n$ set of ordered pairs $s_1=\{(c_1,f_1),(c_1,f_2) ...(c_1,f_m)\}$, $s_2=\{(c_2,f_1),(c_2,f_2) ...(c_2,f_m)\}$, $s_3=\{(c_3,f_1),(c_3,f_2) ...(c_3,f_m)\}$, .... $s_n=\{(c_n,f_1)(c_n,f_2) ...
-4
votes
1answer
504 views

Prove that the problem of rectilinear picture compression is np-complete

I need a demonstration that the rectilinear picture compression is NP-hard, I know that this fact was proven using 3SAT by Masek in 1978 but I can't find the paper.
-4
votes
1answer
100 views

Example of decidable NP-hard problem that is not NP-complete [closed]

I am looking for an example of a decision problem which fulfills the following conditions: 1. It is decidable 2. It is NP-hard 3. It is not NP-complete All my search attempts yielded examples that ...
-4
votes
1answer
62 views

Proving NP-complete problem

Suppose the following problem: Given an undirected graph G=(V,E), is it possible to choose a subset V' of vertex set V, such that deleting it removes all triangles (cycles of length 3), where |V'| is ...
-4
votes
1answer
219 views

NP-completeness of one generalized subset sum problem (target sum belongs to interval) [closed]

I need to prove that decision problem: for a given set of positive integers $a_1, ..., a_n$, does it exist a subset that sums up to a value within interval $[\frac{1}{2}\sum a_i; \frac{1}{2}\sum a_i+...
-4
votes
2answers
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 ...
-4
votes
1answer
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, ...
-5
votes
1answer
560 views

Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
-5
votes
2answers
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 ...
-5
votes
1answer
89 views

NP hard? Maximize the average for a subset of numbers

Given a set of real numbers, choose a subset to maximize the average subject to the average not exceeding a given threshold. Is it NP hard? I think so, but I cannot come out with a proof. Thanks a ...
-5
votes
2answers
624 views

open problems on $NP$-complete? [closed]

How can we find the list of open problems on $NP$-comlpete?