# Questions tagged [np-complete]

Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

620 questions
Filter by
Sorted by
Tagged with
9 views

### What is the time complexity to finding the least weight for Hamiltonian cycle in complete graph without finding best tour?

As we know finding the best tour in complete graph with n nodes, or the Traveling Salesperson Problem solved by the dynamic programming algorithm in $n^2.2^n$ time ...
33 views

96 views

### I need to prove that this Harry Potter problem is NP-Hard. To what problem can it be compared for reduction?

Harry Potter is looking for a bowtruckle that is hiding in a graph and has made itself invisible. Harry tries to find the bowtruckle by casting the spell rivilio trullio while aiming his wand at a ...
56 views

### Understanding our prof's definition of P vs NP

(I have read a lot of online articles, including on MO, SO, etc. but my question stays) We have the following definitions: ...
9 views

### Prove that specific language L is NP-complete and that L $\leq _p$ 3-Colorability

Let $\phi$ be a 3CNF-Boolean formula. An $\neq$-assignment to the variables of $\phi$ is one where each clause contains two literals with unequal truth values. In other words, an $\neq$-assignment ...
349 views

### How to reduce SUBSET-SUM with integers to SUBSET-SUM with non-negative integers?

The subset sum problem is as follows: Given a sequence of integers $\mathcal S=(a_1, ..., a_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose ...
51 views

### Variant of Clique Problem

Given a graph $G$, we say a subset of vertices $S$ is a "good" clique if $S$ itself is a clique and for any vertex $v \in G$, there is a vertex $u \in S$ such that $v$ is adjacent to $u$. I'...
1 vote
14 views

### NP-hardness via polynomial time reduction

I am trying to show a decision problem is NP-complete, using a polynomial-time reduction. As this is a homework question I won't post the exact question but the gist is this: "Let $k\in\mathbb{N}$...
17 views

### Prove NP-completeness of Connected Vertex Cover Problem

Connected Vertex Cover problem is to determine whether a (undirected) graph $G = (V,E)$ contains a $k$-vertex cover $V′$ with $G[V′]$ connected. I know to prove its NP-completeness requires finding ...
167 views

### Karp Reducing Between Problem X and Partition Problem To Show NP-Completeness

I am supposed to show that the following problem is NP-complete by Karp reducing it to the Partition Problem. Problem X is: Given: D vaccine doses, n age groups, a1 to an as input, where age group k ...
48 views

### Why isn't Quadratic Congruences trivially solvable in polynomial time?

The Quadratic Congruences problem asks if for constants $a$, $b$, and $c$, does there exist $x$ such that $x<c$ and $x^2 \equiv a\mod b$? This problem is known to be NP-complete. However I can't ...
44 views

### How we reduce NP problems?

Assume that P1, P2,..., Pn are NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be ...
38 views

### Complexity/ polynomial time - If a problem has $x + y - 1 \choose y-1$ possible solutions & each can be evaluated in polytime, is that in P?

I am trying to show the complexity of a problem and each instance's size is defined by parameters $x$ and $y$. For a given instance, I know there are $x+y-1 \choose y-1$ possible solutions. Each of ...
89 views

### Given this theorem, Why is Subgraph Isomorphism NP hard and not polynomial?

So, I read the following Theorem by Matousek and Thomas: Given graphs $G$ and $H$, we want to check if there is a subgraph $S \subseteq H$ such that $S$ and $G$ are isomorphic. Then, if the maximum ...
25 views

### Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
1 vote
65 views

### Is this egyptian fractions problem NP-complete?

Given a set of positive integers $\ M=${$\ a_1,a_2,\cdots ,a_k\$} and a rational number $\ r\$ , is the following decision problem NP-complete ? Is there a subset $S\subset M$ with \sum_{p\in S} \...
73 views

### Reduction of hard to easy problem and vice versa

$A\: \leq_m B$ means means $A$ cannot be harder than $B$ that means $B$ is atleast as hard as $A.$ And also I know that "If $B$ is easy then $A$ is easy" and "If $A$ is hard then $B$ ... 43 views

### Conversion NPH problem reduction

To prove any problem $R$ is NPH then take any known NPH problem $L$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $L$, then prepare another instance ... 1 vote
95 views

### Certifier in the subgraph isomorphism problem

In the subgraph isomorphism problem we need to establish a certifier where we can map the edges from induced map to the original map. And it will take polynomial time to achieve. Does this mean that ...
35 views

### Are two optimization problems equivalent?

In complexity theory. There are two optimization problems. If decision problems associted with them are all NPC, then we know the two decision problem are equivalent. Are two optimization problems ...
1 vote
113 views

### Is (3,3)-NAE-SAT NP-complete?

In this question I assume the following: in either $(i,j)$-SAT or $(i,j)$-NAE-SAT, every clause has exactly $i$ literals, and a given variable appears at most $j$ times in the entire formula. NAE ...
26 views

### Partition problem with additional constraints

I have read about the partition problem a.k.a. the easiest hard problem. I am currently working on a game where there are, say, 180 players that need to be organized into 30 teams with 6 players in ...
50 views

### Maximum independent set in a graph versus maximum matching in the line graph

As regards this post Maximal independent sets in a graph $G$ versus maximal matchings in the line graph $L(G)$ -- and in particular, the comments under this answer https://math.stackexchange.com/a/...
34 views

### Proofing Decide Injective Coloring Problem is NP-complete for perfect elimination bipartite graphs?

So the proof goes like this For a graph $G=(V,E)$, $V=\{v_1,v_2,...,v_n\}$, $E=\{e_1,e_2,...,e_m\}$ having a chromatic number $X(G)$ we construct a perfect elimination bipartite graph $H$, using ...
The First-Fit-Decreasing algorithm solves the bin packing decision problem for given weights $w_1,\dotsc,w_n\in [0,1]$ and number of bins $k$ in quadratic time. This would mean that the bin packing ...