We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
-4
votes
1answer
61 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
209 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
86 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
436 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
554 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
613 views

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

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