# 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,409 questions
Filter by
Sorted by
Tagged with
2k views

### For what special cases does this vertex cover algorithm fail or work?

I'm trying to find a polynomial time algorithm for finding the minimum vertex cover for a graph. I've written the algorithm below; I know this problem is $\mathsf{NP}$-hard, which means there are ...
2k views

### How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
401 views

### Modified Clique Problem

We know CLIQUE and HALF-CLIQUE problems are NP-complete. Now consider the class of graphs (let's call it $\mathcal{G}_{2K}$) where a graph $G=(V,E)$ is a member of $\mathcal{G}_{2K}$ iff $G$ has two ...
110 views

### Prove TILING is NP-Complete

I have a homework task to show that $\mathrm{TILING} = \{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\}$, where $t\in T$ is $C^4$ for some color set $C$, ...
926 views

### Strongly NP-hard problems and Dynamic Programming

Dynamic Programming seems to result in good performance algorithms for Weakly NP-hard Problems. Two examples are Subset Sum Problem and 0-1 Knapsack Problem, both problems are solvable in pseudo-...
695 views

### How to prove that finding math proofs is $\text{NP}$-hard?

This is Exercise 2.11 of the book "Computational Complexity: A Modern Approach" by Arora and Barak. Mathematics can be axiomatized using for example the Zermelo-Frankel system, which has a ...
881 views

### NP-complete reduction proof -- graph problem

While studying proofs of NP-completeness via reduction, I saw a seemingly challenging problem: You are given some undirected graph $G = (V, E)$, along with a set $S$ which consists of 0 or more pairs ...
2k views

### Reducing directed hamiltonian cycle to graph coloring

The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring ...
3k views

### Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

I'm a little stuck on this question, any help would be appreciated! Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is ...
163 views

### Select at least one from each category to minimize union, NP-hard problem?

I have this problem that is very similar to the minimum k-union problem: Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category. The problem is ...
125 views

### Partition into paths in a Directed Acyclic Graphs

I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths. When $b_i=1$ for all the ...
99 views

### Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
138 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 ...
320 views

### Path in an edge-weighted undirected graph

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary....
8k views

### Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete

I tried to solve the above NP-completeness exercise by making a bipartite graph from a general one (undirected) by inserting a vertice in the middle of every edge of the first (general) graph. This ...
282 views

### Is the buckets of water problem in NP?

Continuing from this question: the buckets of water problem. (All the definitions can be found there, so I will not repeat them). As seen there by Yuval's answer, the problem is NP-Hard. I was ...
536 views

265 views

### Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?

Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional ...
100 views

### Rearrange a sequence of real numbers to satisfy polynomial inequalities

Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$). Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$...
783 views

### What would an exponential reduction from an NP-complete problem to P signify?

Taking an NP-complete problem like vertex cover if we can find a reduction which is exponential and not polynomial and the reduction we do to a problem can be solved in polynomial time, then what ...
2k views

### Reduction to Hamiltonian cycle

Given that the Hamiltonian cycle problem is NP-complete, I want to prove that the following problem is NP-complete: Given an undirected graph $G(V,E)$ and vertices $s,t\in V$, does there exist a ...
170 views

### Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to ...
1k views

### Pseudo-polynomial time algorithm for NP-Complete Problems

For problems like Knapsack there is a pseudo-polynomial time algorithm and it is NP-complete. So we reduce every other problem in NP in polytime to Knapsack. But why don't we have then a pseudo-...
173 views

### Word tiling, where you must use each tile exactly once

Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of ...
3k views

### 0/1 Integer Programming and Karp's Reduction

I have been reading Karp's famous paper on the NP-Completeness of different problems, Reducibility among combinatorial problems, and I have a question on the reduction from SAT to 0/1 Integer ...
284 views

### How does the problem of having a coffee-machine close relate to vertex cover?

Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that ...
191 views

### Is the following NP-complete?

I have encountered the following problem. We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $[1..Y]$ and horizontal axis $[1..X]$. We can perform the action of ...
699 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 ...
638 views

### Time complexity of a problem inspired by palindromes

This was inspired by Bradshaw's question originally posted on Math.SatckExchange. EVEN PALINDROME: Input: Given a list of strings $[v_1, v_2, ... ,v_n]$ where $\Sigma |v_i|$ is even number. ...
174 views

### What does Cellular Automata Pre-image problem actually means?

I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata. In the 2nd page he lists three NP-Complete ...