# 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.

1,087 questions
Filter by
Sorted by
Tagged with
12 views

### NP-Complete reductionTrue/False question explanation

Why is the above statement true? my understanding is: (1)3SAT reduces to X implies X is NP-complete or harder. (2)Set Cover reduces to X implies X is neither NP-Complete nor harder. This ...
29 views

### Disjoint paths in digraphs is NP-complete

In the article: S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraphs homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121. link: https://www.sciencedirect.com/science/article/pii/...
35 views

### In which paper is written that you can transform one problem to another to show NP-completeness?

For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard: Post I am searching for a scientific paper to cite where it is written, that ...
52 views

### An NP-hard problem reduces to its complement?

I found this statement in a true/false test section: Could someone explain in laymans why this is a true statement? My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
40 views

### Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k) polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
88 views

### Vertex cover with covering radius 2

Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices? A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
2k views

### Reduce Vertex Cover with size k to Vertex Cover with size n/2

Disclaimer: This is a homework question. I would like to reduce vertex cover problem to the following problem: $$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$ I have divided the ...
69 views

### triangle inequality TSP is NP-complete?

I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric ...
55 views

39 views

### A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
28 views

### how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
125 views

45 views

### Finding a vertex coverage that is also an independent set

Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?
33 views

### Another Subset sum problem

Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.