Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

Filter by
Sorted by
Tagged with
1
vote
1answer
1k views

Set cover problem and the existence of such cover

In the set cover problem we want to find in the $\mathbb{S} \subset 2^\mathbb{U}$ the subset $\{s_i\}_{1..k}$, such that $\cup s_i = \mathbb{U}$ for given $K$, where $k \le K$. But how to reduce the ...
1
vote
2answers
680 views

Prove “almost clique” is NP complete

Given $G=(V,E)$, undirected graph, a group of vertices $S$ is called almost clique if by adding a single edge, $S$ becomes a clique. Consider the language: $L=\{\langle G,t\rangle \mid \text{the ...
1
vote
1answer
2k views

Prove Partition is NP-Complete using that SubsetSum so is it

The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete. The ...
1
vote
1answer
273 views

Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones

select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones
1
vote
3answers
388 views

Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
1
vote
1answer
478 views

Set cover problem with sets of size 2

I have a question about the Set Cover problem: If I get a universe $U$, and $m$ subsets of size exactly $2$, and an integer $k$. Is this problem is still NP-C or I can solve it on a polynomial time? ...
1
vote
1answer
175 views

Show Resource Allocation Problem is NP-Complete

We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...
1
vote
0answers
258 views

Reducing a problem with two knapsack that needs equal number of items from Knapsack?

I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness. The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from ...
1
vote
1answer
145 views

Quadratic Diophantine equation - Polynomial Time Cases

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$ a*x^2+b*y= c $$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete. The solution (x, y) are ...
1
vote
0answers
143 views

Saxe's proof of 1-embeddability

I've been reading Saxe's proof that 1-embeddability of integer weighted graphs is NP-Complete (http://www.math.columbia.edu/~dpt/RigidityREU/Saxe79EmbedNPHard.pdf Theorem 3.2). I don't understand how ...
0
votes
1answer
214 views

Complexity class (P/NP) variants of Hamiltonian paths problems

I know that the following problems related to Hamiltonian paths in graph are NP-complete: Undirected Hamiltonian circuit: Given an undirected graph, does it has a cycle that passes through each node ...
0
votes
1answer
305 views

NP-complete promise problems? [closed]

Are there any good examples of promise problems that are NP complete?
0
votes
1answer
37 views

Karp hardness of an equidistant set in digraph

Following the success of the undirected version: Karp hardness of an equidistant vertex set Inspired by the success of this long ago question: NP-hardness of problem with indices and subsets We ...
0
votes
1answer
181 views

NP hardness of unique Puzzle Generation

Introduction For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The ...
-1
votes
2answers
445 views

Some inference about NP

this is my first question on this site. I‌ recently, study on NP. I have some confusion about this Topic, and want to propose my inference and some one verify me. I) each NP problem can be solved ...

1 2 3 4