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

### Generalizations of integer-programming for the polynomial hierarchy?

Integer programming is known to be NP-complete. We also know that each class in the polynomial hierarchy contains elements not contained in the ones below, so Integer programming is not complete for ...
• 4,052
45 views

### showing NP completeness for XS

the XS problem: Input: n final sets and a number k (final sets - finite set of numbers, and k's value can be at most n). Question: Are there k sets in the n final ones that are not pairwise disjoint? ...
• 27
1k views

### Why can't we prove SAT is NP complete just using the Tseytin Transformation?

The Cook Levin theorem proves SAT is NP-Complete, but it is fairly complicated, non-constructive and uses a Turing machine. I am confused as to why just the Tseytin Transformation does not imply/prove ...
• 43
97 views

### Is this set cover problem NP-complete? (creating a list of best movies per year)

Let $X$ be a finite set. Let $\mathcal{F}$ be a family of subsets of $X$. Assume each set $F\in\mathcal{F}$ is colored with a single color from a set of colors $C$. Is the following problem NP-...
• 53
61 views

### Vertex cover approximation: what's wrong with max-degree heuristic?

For context: the usual greedy approximation algorithm for the minimum vertex cover problem (given a graph, find the smallest set of vertices such that every edge is incident to at least one selected ...
• 141
51 views

### Non-deterministic TM with an oracle to $R$

Let $R$ be the set of all decidable languages. Consider $P^R$. That is, the set of all languages that can be decided via a polynomial time deterministic TM with an oracle to any language $L\in R$. I'd ...
1 vote
22 views

### Help required for an example of a restricted 3,3-SAT problem instance?

"Let r,s-SAT denote the class of instances with exactly r variables per clause and at most s occurrences per variable. We prove the 3,4-SAT result to be the strongest possible and show that 3,3-...
• 745
367 views

### Is 3, 3 satisfiability trivial after all?

Tovey's paper from 1982 clearly states that: Theorem 2.1. Boolean satisfiability is NP-complete when restricted to instances with 2 or 3 variables per clause and at most 3 occurrences per variable. ...
24 views

### 4COL problem with additional constraint on the size

The task is to prove that that 4-coloring of a graph with additional constraint about number of vertices is NP-complete. Constraint: Each color class should contain at least $\frac{1}{5}$ of total ...
• 61
108 views

### Determining whether there's a permutation that satisfies a linear equation

Given a positive integer $n$ and integer coefficients $c_1, c_2, c_3, c_4,..., c_n$, the goal would be to find a $\sigma \in S_n$ ($S_n$ is the group of permutations on $\{1,2,...,N\}$) such that: \...
• 173
77 views

• 161
1 vote
77 views

### Graph Coloring Decision Problem Reduction to Prove NP-Complete

I am doing research into NP-Complete problems and more specifically started looking into the Graph Coloring Decision Problem or the k-Coloring problem, as described here: Given a graph $G = (V, E)$ ...
• 11
1 vote
52 views

### Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
• 113
37 views

### Satisfiability of a boolean formula with two occurrences of each variable with a special ordering

I am interested in the complexity of a special case of the boolean satisfiability problem: We are given a boolean formula, consisting only of the logical operators $\land$ and $\lor$ (that can be ...
• 161
28 views

### Show that it is Np-hard to determine whether a given graph has the crossing number k

I want to prove that this problem to find whether the crossing number of any given graph is K or not, is NP-Hard. I don't know how to do this. Can someone help me with this ?
45 views

### If $P=NP$, then $LCP \in P$

I want to prove that if we assume $P=NP$, then we can find the longest cycle (maximal number of vertices, no repeated edges, only repeated vertex is the starting one) in an undirected graph in ...
20 views

### Kernelization For Odd Cycle Transversal Problem on Perfect Graphs

This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
30 views

### How do you show that Cosmic Kite Problem is NP complete?

A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique. Cosmic Kite as decision problem Input: a graph G = (V, E) ...
1k views

### Why is 3-SAT used for proving NP-Completeness so often?

I was wondering why 3-SAT is often chosen as the candidate problem from which one reduces from to prove the NP-completeness of another algorithm. I've seen it justified in places such as K&T by ...
40 views

### Polynomial-Time Solvability Through NP-Completeness Reductions

Let A and B be NP-complete problems. Suppose I have established reductions from problem A to problem B and vice versa. Now, considering a specific instance (or set of instances) of problem A that can ...
• 121
1 vote
142 views

### Prove "Vertex Cover OR Clique" is NP complete

Instance: An undirected graph $G$ and a positive integer $k$ Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$? Obviously, this problem is solved by polynomial ...
96 views

### Quasi polynomial algorithm for np complete problem

I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...
• 11
35 views

### If this variant of Subset Product remains NP-complete, what other inputs could give me exponential time?

Given $N$ a whole number and a set $S$ of divisors of N, where no repetition is allowed. Decide if there is a combination of divisors with a product equal to $N$. Remove non-divisors from $S$. Remove ...
• 321
73 views

### Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall ...
1 vote
62 views

### Does the Subset Product Problem remain NP-complete if repetition in S is not allowed?

Just curioius, I wanted to know when $S$ ={set of divisors of N} and we're given $N$ a target product. Our goal is to decide if a combination in $S$ has product equal to N. Does the problem remain NP-...
• 321
29 views

### Is every problem which can be solved by an algorithm using polynomial space in PSPACE?

I recently learned about the definition of PSPACE problems, which are a subset of decision problems that can be solved by using polynomial space. However, one thing I don't understand is when I asked ...
3k views

### Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?

Are there languages L1 ⊆ L2 ⊆ L3 where L1 and L3 are NP-Complete languages and L2 ∈ P? Would this imply P=NP? Thanks
• 349
32 views

### Is this version of SAT NP-Complete?

Given a SAT instance such that: Each clause is of length at most 4. Negative literal occurs only in clauses of length=2. Each length 2 clause has at most 1 negative literal. Is this version of SAT ...
• 745
48 views

### Show 3-colorable graph with hamiltonian cycle is NP-Complete

The language is : $3COLORHC = \{<G> | \text{ G is an undirected 3-colorable graph that contains Hamiltonian cycle} \}$ I was asked to show that this language is NP-Complete. Showing that the ...
• 275
1 vote
84 views

• 73
99 views

### Double Dominating Set NP-Complete

How do i show that Double Dominanting Set is NP-Complete by reducing Dominating Set to it i have thought by adding a edge but my solution is not correct Input is an undirected graph and a target. The ...
360 views

### What do we know about the asymptotic proportion of "easy" instances of NP-complete problems

In practice, it seems that many NP-hard problems "usually" lead to easy instances, in the sense that a commercial solver can handle them reasonably. A few past questions on this topic (see ...
392 views

### Algorithm that generates verification program from solution program of NP problem

I don't know complexity class theory well so I might make some categorical errors, but I will try to ask this question anyways. Suppose you have written a function in some programming language which ...