# 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.

160 questions
Filter by
Sorted by
Tagged with
112 views

### Seeking Efficient Approximation Algorithm for Adaptation of TSP

Consider the following adaptation of the traveling salesman problem: Given a complete, undirected graph $G$ with nonnegative edge weights, color each vertex either red or blue. Find the shortest ...
375 views

### Reducing co3SAT to UNIQUE-SAT

I am having trouble with this problem: Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq_p UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique ...
121 views

### Are non-trivial sets formed by set operations on NPC sets still in NPC?

I know that from this answer to a question on the class NPC, that NPC is not in general closed under intersection and union. However, the answer used languages which form trivial languages under ...
4k views

### To prove 4-SAT CNF is NP-complete [closed]

To answer the question below, 4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment? I was going to prove that ...
69 views

256 views

### Is this problem NP-hard? Maximizing selected sets so that their union is less than k?

There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union. I'm currently ...
515 views

### Is it allowed to do a binary search with an oracle when proving NP-completeness?

In https://cs.stackexchange.com/a/45524/28999, they do a binary search using an oracle for an NP-Complete problem. They show that the original problem can be reduced to that NP-Complete problem, ...
163 views

### Game tournament program, NP complete?

I have been trying to find a solution both theoretical and practical to my problem but I just can't. The question is you have x players that should play some rounds y of games in groups of 4. Now if a ...
148 views

### Showing a problem on a specific class of graphs is NP-hard

We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but may be polynomial-time solvable for some classes of specific ...
570 views

### Prove finding a near clique is NP-complete

An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if ...
91 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 ...
100 views

### Transforming 3 SAT to Simultaneous In-Congruence Problem?

Garey and Jhonson mentions that a 3-SAT Problem can be transformed to another NP-Complete Problem - Simultaneous incongruences (AN2): Given a collection $[(a_1,b_1),…,(a_n,b_n)]$ of ordered pairs of ...
143 views

### A Query regarding Quadratic Residuocity Problem

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: $$x^2\equiv q \pmod{n}.$$...
157 views

### Check if K-Sum Variation is NP-Complete

Problem Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$. Question This problem came from evaluating some scheduling algorithms that I am ...
1k views

### Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs

I'm trying to solve a problem for class that is stated like so: A bipartite graph is an undirected graph in which every cycle has even length. We attempt to show that the Hamiltonian cycle (a ...
1k views

278 views

I have two sets $A$ and $B$, I want to reduce $A$ to $B$ and $B$ to $A$. Formulas consist of a finite set of variables $\mathcal{V}$. An assignment $\sigma$ assigns truth values to each variable in $... 2answers 656 views ### Prove “almost clique” is NP complete Given$G=(V,E)$, undirected graph, a group of vertices$S$is called almost clique if by adding a single edge,$S$becomes a clique. Consider the language:$L=\{\langle G,t\rangle \mid \text{the ...
I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness. The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from ...