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
2answers
72 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 ...
0
votes
1answer
23 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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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....
3
votes
1answer
34 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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
1answer
47 views

Simple Hamiltonian cycle reduction

HAMPATH Input: An undirected graph $G$ and 2 nodes $s, t$ Question: Does G contain a Hamiltonian path from $s$ to $t$? HAMCYCLE Input: A undirected graph $G$ and a nodes $s$ ...
2
votes
1answer
74 views

Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G

In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following: Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving ...
1
vote
2answers
49 views

Reduce subset sum to 3SAT

How to do it? I'm not asking the solution for the proof of why subset sum is NPC, but rather the opposite reduction
3
votes
1answer
46 views

Techniques for proving NP-completeness

I've been reading Garey-Johnson book Computers and Intractability and I am focusin on Section 3.2, Techniques for proving NP-completeness. In these definitions and explanations nothing is formally ...
0
votes
1answer
51 views

Are there any “complete” languages in $coNP -NP$?

Suppose $coNP \neq NP$ language B would be called "complete" in $coNP-NP$ if: $B\in coNP - NP$ $A\in coNP-NP \implies A\leq_pB$ Are there any "complete" languages in $coNP - NP$?
0
votes
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 ...
2
votes
0answers
69 views

Proving NP-completeness of an extension in List Coloring Problem

In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
12
votes
2answers
3k views

Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially ...
1
vote
1answer
35 views

Reducing 3 SAT to 3 SET PACKING

I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise ...
1
vote
1answer
33 views

Complexity of “half cycle”

I'm working on the following problem: HALFCYCLE (HALFC): Input: A directed graph $G = (V,E)$. Output: Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$. Prove that if $\...
0
votes
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 ...
3
votes
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 ...
0
votes
1answer
53 views

pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
0
votes
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 ...
0
votes
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 ...
2
votes
1answer
35 views

Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
3
votes
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) ...
2
votes
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 ...
1
vote
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 ...
2
votes
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. ...
1
vote
3answers
65 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. ...
3
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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: ...
0
votes
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 ...
0
votes
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 ...
4
votes
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 ...
1
vote
1answer
37 views

Reducing CLIQUE to Super Connector problem

I am trying to show that our problem is NP-Complete by reducing the known problem CLIQUE to our problem. Regular CLIQUE problem: Input: An undirected graph $G$ and a positive integer $K$. ...
1
vote
2answers
106 views

Reduce 4-SAT to 5-SAT

given is a reduction from 4-SAT to 5-SAT. How is it possible to describe such a function? I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.
1
vote
1answer
34 views

If a problem Q is NP complete, is another problem reducible to Q also NP complete?

Let's say $\mathcal{P}$ is a yes/no prolem with an existing reduction to the problem $\mathcal{Q}$ (with time complexity $\mathcal{O}(n^2)$). $\mathcal{Q}$ is NP complete. Does this mean that $\...
3
votes
1answer
34 views

Finding a language that is $NP^L$-complete

I'm trying to prove a theorem and as a lemma I would like to identify an $NP^L$-complete language. I was thinking something like a machine that can decide $SAT$ equipped with an oracle for $L$ can ...
7
votes
1answer
1k views

Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

I saw an image that describes the relations of P, NP, NP-Hard and NP-Complete which look like this : https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg I wonder if ...
5
votes
1answer
157 views

Prove that “Finishing the degree in three years” problem is NP-Complete

I was asked in an interview the following question: We'll define the "Finishing the degree in three years" problem in the following manner: Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, ...
0
votes
1answer
169 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
vote
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 ...
2
votes
1answer
99 views

Proving NP hardness in Puzzle with SAT reduction

Introduction 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 algorithm follows an infinite language based on ...
0
votes
1answer
49 views

Valid method to prove NP completeness of a problem?

Suppose we are given that checking if there is a Hamiltonian path in a graph is NP Complete (HP problem). I want to prove that given a graph, node x, and node y, checking if there is a Hamiltonian ...
-1
votes
1answer
31 views

3-Coloring Graph problem

Can we prove that the 3 coloring graph problem (where no two adjacent nodes have same color) is NP instead of NP-complete? $$\mathrm{3COLOR} = \{\langle G \rangle \mid G \text{ is colorable with 3 ...
2
votes
1answer
113 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 ...
0
votes
0answers
22 views

What would be a good way to prove NP-Completeness of Min-satisfiablity problem

I am trying to prove the NP-Completeness of Min-satisfiability problem which can be defined as: Given a CNF formula (Set of clauses of 1 or more boolean variables) and a number x, there exists a ...
4
votes
1answer
60 views

Is this problem that's similar to integer linear programming also an NP-complete problem?

I've come across this problem while trying to work out a table-formatting algorithm. It's very similar to standard linear programming (though it uses $>$ instead of $<$; I'm not extremely ...