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

171 questions
Filter by
Sorted by
Tagged with
445 views

### Proving that finding wheel subgraphs is NP-complete

Can you help me with this problem ? Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ ...
1k views

### Reduction from PARTITION to 3PARTITION

I'm considering the problem (a variant of 3-PARTITION, see here) with description Instance: Set of positive integers $A={w_{1},...,w_{n}}$ with $S(A)=\sum\limits_{i=1}^{n}w_{i} = 3m$. ...
980 views

### Reducing from Hamiltonian Cycle problem to the Graph Wheel problem [duplicate]

EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this ...
642 views

### NP-completeness of graph isomorphism through edge contractions with an edge validity condition

Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
105 views

### Karp hardness of searching for a matching cut

Follow-up question in the series: Karp hardness of searching for a matching erosion Karp hardness of searching for a matching split Maximum Matching Cut problem Input: An undirected graph $G(V, E)$ ...
39 views

### Karp hardness of searching for a matching erosion

First, read the previous question: Karp hardness of searching for a matching cut As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
76 views

### Karp hardness of searching for a matching split

UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
68 views

140 views

### NP-Complete problem proof

I have an exam in two days and I am not sure if I have understood correctly the way of proving np-completness and how to pick a known np-hard problem to reduce it. Bellow I present a problem which I ...
275 views

### Subset sum to 0/1 knapsack

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.
1k views

### Decision Problem vs. Optimization Problem [duplicate]

Is the following statement correct? If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.
49 views

### Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

i don't understand the following: If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
443 views

### Is the weighted transitive reduction problem NP-hard?

The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$. When $E^t \subseteq E$ it is NP-complete. ...
15k views

### Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
24k views

### Are there NP problems, not in P and not NP Complete?

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but ...
12k views

### are NP Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. ...
9k views

### Rule of thumb to know if a problem could be NP-complete

This question was inspired by a comment on StackOverflow. Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like ...
20k views

7k views

### Reduction from set cover problem to vertex cover problem

Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I ...
769 views

2k views

### Is it proven that quantum computation is no better at solving NP complete problems than classical computation?

Is it proven that quantum computation is no better at solving NP complete problems than classical computation or it's just believed?
967 views

### Polytime algorithm for SUBSET-SUM assuming P=NP

In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in ...
3k views

### Can a subset of an NP-complete problem be in P?

The problem is NP-complete (proven) for all input data (without exception). We assume that P != NP. Is it possible that there is an (infinitely large) subset of the problem, for which this subset is ...
Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating $\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$. I understand the ...