# 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,006 questions
Filter by
Sorted by
Tagged with
0answers
4 views

### Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete?

Suppose we have a set of variables $V$. We also have a set of equations $E$, which are sets of at least two variables. We don't know anything about these equations, except if we know all but one of ...
2answers
77 views

### TSP Variant — Colored Path

Recently I came up with a traveling-salesman-esque problem. As usual, we have $n$ vertices, and a weighted edge between any two vertices. However, each vertex is associated with a color, which may be ...
2answers
134 views

### Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
1answer
24 views

### Is the reduction for HAMPATH to HAMCYCLE and UHAMPATH to UHAMCYCLE the same?

HAMPATH/UHAMPATH is A directed / undirected graph G and 2 nodes s and t and is there a hamilton path from s to t? Likewise with HAMCYCLE/UHAMCYCLE but has a hamilton cycle on $G'$ The reduction ...
1answer
18 views

### UNDIRECTED HAMCYCLE to HAMPATH reduction

I'll define the problems UHAMPATH Input: A undirected graph G and 2 nodes, s and t Question: Is there a hamiltonian path from s to t in G? UHAMCYCLE Input: A undirected graph G ...
1answer
23 views

### A doubt on converting NOT gate to CNF formula

For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$. My ...
2answers
6k views

### Subgraph isomorphism reduction from the Clique problem

I was trying to understand the Wikipedia proof for NP-completeness of subgraph isomorphism by reduction from the clique problem. It's really just one sentence: Let $H$ be the complete graph $K_k$; ...
1answer
9 views

### How to use c-gap problems to prove inapproximability?

Suppose there is a specific set function with some properties - $f=2^V\to \mathcal{R}$. It is known that the following problem is NP-Hard: Find $S\subseteq V, |S|\leq k$ such that $f(S)$ is maximized....
1answer
83 views

### Embedding trees of diameter four is NP-hard

Suppose that $T$ is a tree of diameter four and $G$ is a graph. Deciding, whether $T$ can be injectively mapped to $G$ is NP-hard (there is a simple reduction from the problem of finding an ...
3answers
19k views

### Knapsack problem — NP-complete despite dynamic programming solution?

Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right? I have read it is actually an NP-complete problem, though, which ...
1answer
35 views

### Is this variation of set-cover NP-hard to approximate?

The classic set-cover problem is described as follows: Let $S = \{s_1, ..., s_n\}$ be a target set, and let $\Lambda = \{A_1, ..., A_m: A_i \subset S\}$ be a collection of subsets of $S$. The ...
0answers
31 views

### Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?

I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ...
1answer
51 views

### How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

I have proved the decision version of my problem be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just to compare the obtained minimum (or ...
3answers
78 views

### How Reduction works in proving NP-Hard?

A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq_P X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq_P X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard. I also ...
1answer
303 views

2answers
2k views

### Poly-time reduction from ILP to SAT?

So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP ...
0answers
69 views

1answer
41 views

### Prove Subset-Sum is NP-complete - Alternative reduction?

It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the ...
1answer
122 views

### Proving NP completeness of maximal length path

I have this question to answer: For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
2answers
53 views

### Proving a problem as NP-complete

According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs ...
1answer
45 views

### Time complexity of subset sum problem with reals instead?

It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete ...
1answer
114 views

### Is maximum-leaves spanning tree np-complete?

How can we show that a maximum-leaves spanning tree is NP-complete? what other np-complete problem we can use as our reduction base? (maximum-leaves spanning tree: does G have a spanning tree with at ...
1answer
87 views

### P vs NP question from GeeksforGeeks

From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/ Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to ...
2answers
136 views

### Why isn't the Generalized Super Mario Bros. obviously in NP?

It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) ...
1answer
31 views

### Weak NP-completeness

I know that the Knapsack problem is weakly NP-complete. I also notice that on Wikipedia: "A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it ...
1answer
30 views

### Reduction from NP-complete problem to unknown complexity problem and vice-versa

Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity. Question: If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required ...
2answers
3k views

### reduction from SET-COVER to VERTEX-COVER

I've come with an idea for reduction from the set-cover problem to the vertex-cover problem, But I'm not sure if this reduction is correct. I saw in this post's comments that "There cannot be a nice ...
0answers
25 views

### NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if: They are vertex-disjoint. Each one is itself an induced path. No edge connects two vertices of two different paths. ...
3answers
1k views

### Prove NP-completeness for union of NP-complete language and language in P

Given disjoint languages $X$ and $Y$, where $X$ is NP-complete and $Y\in P$ , how do I prove that $X\cup Y$ is NP-complete? My idea is to prove that $(X\cup Y)\in NP$ and then prove that $X\cup Y$ is ...
1answer
85 views

### NP-completeness of Induced disjoint paths

In graph theory, it is well-known to be NP-complete the problem of given a set of $k$ pairs of source-sink, deciding whether there exists $k$ vertex-disjoint paths connecting these pairs. Our problem ...
0answers
74 views

### Matrix covering by squares

I wonder about the following decision problem : Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$. Question: is it possible to cover all the ones of the ...
3answers
66 views

### How to solve the optimization of bin packing using the decision version

Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins. ...
1answer
36 views

### What are the current state of art approximation algorithm for NP-Hard problems? [closed]

I came cross some works try to use deep learning to approximate NP-Hard https://arxiv.org/pdf/1810.10659.pdf Though the paper seems to have very good results but based on the citations. I'm quit ...
1answer
48 views

### Parity Hamiltonian path problem

Wikipedia says that Hamiltonian path problem is NPC, but Parity Hamiltonian path problem (i.e., is there an odd amount of hamiltonian path) is P. Does a reduction from, e.g., SAT, to HPP, unavoidably ...
1answer
41 views

### Reduction from minimum dominating set to the set cover

To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem. For example to find the MDS of the graph G: We can create an instance of the Set Cover problem by: ...
1answer
69 views

### Subset with modified condition, is it still NP-complete? [closed]

So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard. The given problem I have is subset sum. However, the conditions have been ...
0answers
37 views

### Is it NP-complete to test if a graph contains $t$ $k$-cliques?

Let $(G,t,k)$ - a graph with $t$ cliques with $k$ vertices (there are $t$ cliques of size $k$ in graph $G$), for $t,k > 100$. How to prove that $(G,t,k)$ is NP-complete? It is obvious that it is ...