# 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,102 questions
Filter by
Sorted by
Tagged with
17 views

### Minimum total waiting time for arrivals/durations

I have come up with the following problem, and cannot seem to find an effective way of solving it: Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration ...
6 views

### Are all NP-complete languages downward self-reducible?

Arora-Barak says that using the Cook-Levin reduction, one can show that all NP-complete problems are downward self-reducible. I know that SAT is downward self-reducible but I am not able to see how we ...
24 views

### Obtaining a graph with no cycles after removing k edges

I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
38 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 ...
7k views

### P = NP clarification

Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example. My understanding of P=NP question is that, given the optimal solution of a difficult problem,...
15 views

### polynomial reduction & co np complete

I would like to know how we can demonstrate these two problems : $A \leqslant_p B$ implies $\overline A \leqslant_p \overline B$ The complement of 3-SAT is co-NP-complete
39 views

68 views

### Is SAT a single language or a union of languages?

I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
91 views

### Coloring an interval graph with weights

I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of ...
191 views

### Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E)$, and as long as you ...
56 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 ...
162 views

### You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?

My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover ...
14 views

### Which instances of Exact Cover are considered hard?

In the Exact Cover formulation there are $N$ variables and $M$ "clauses''. For the special case when each clause contains exactly $3$ variables it is called 3-Exact Cover. Now, I've read in articles ...
66 views

### Show that a problem is NP-Complete

The problem is, K_longestPath: We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each ...
79 views

### P Vs NP can never be proven one way or the other!

Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem. And since if we prove that any problem in NP is a P that would mean that we have NP=P. ...
43 views

### Encoding order relations in CNF

I want convert timetable scheduling problems to SAT problems. Suppose there are $t$ time slots and $c$ classes. I will define $t\times c$ variables $x_{ij}$, which is true iff class $j$ takes place in ...
74 views

### triangle inequality TSP is NP-complete?

I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric ...
59 views

### If any problem in NP is not in P then NP C ∩ P = ∅

If any problem in NP is not in P then NPC ∩ P = ∅ The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction. I have not clear ...
47 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 ...
77 views

### NP-completeness for integer linear program

This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
50 views

### Independent set problem

I'm referring to a post here,https://www.transtutors.com/questions/suppose-that-someone-gives-you-a-black-box-algorithm-a-that-takes-an-undirected-grap-1706946.htm# Question: Suppose that someone ...
55 views

### Prove the Droid Trader Problem is NP-complete

This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos. A player in the game controls a spaceship and is trying to make money buying and selling droids on ...
A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding ...