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.

Filter by
Sorted by
Tagged with
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
69 views

Given three languages L1 L2 L3 that do not intirsect could one be TR and the other TD and the third neither

where $L_{1} \cup L_{2} \cup L_{3} = \sum^{*}$ and $L_{1} \cap L_{2} = \emptyset$ and $L_{2} \cap L_{3} = \emptyset$ and $L_{1} \cap L_{3} = \emptyset$ is it possible that $L_{1}$ is decidable, $L_{...
-2
votes
2answers
2k views

complexity of decision problems vs computing functions [closed]

This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens ...
11
votes
1answer
469 views

Independent set on cubic triangle-free graphs

I know that maximum independent set on cubic triangle-free graphs is NP-complete. Is it still NP-complete in case we require the independent set to be of size exactly $|V|/2$? Basiclly, YES ...
10
votes
2answers
693 views

Is this classic puzzle book game NP-complete?

There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked ...
8
votes
4answers
3k views

Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?

I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists. Is there a good / quick / easy way to see ...
6
votes
1answer
5k views

Reduce Vertex cover to SAT

I need to reduce the vertex cover problem to a SAT problem, or rather tell whether a vertex cover of size k exists for a given graph, after solving with a SAT solver. I know how to reduce a 3-SAT ...
5
votes
1answer
967 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-...
5
votes
1answer
243 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 ...
5
votes
1answer
908 views

Is set cover still NP-complete if you have a given k?

Set cover is NP-complete given an arbitrary set $U$, a set $S$ of subsets of $U$, and an integer $k$. However, what if $k$ is always a constant 3? Is that problem still NP-complete?
5
votes
3answers
2k views

Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), ...
4
votes
0answers
178 views

Relativization of NP-completeness [duplicate]

This is actually exercise 3.7 from "Computational Complexity: A Modern Approach". I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. I need to show that that exists some ...
4
votes
0answers
170 views

Proof of NP-completeness of graph isomorphism through edge contractions that reduce a metric [duplicate]

Duplicate: NP-completeness of graph isomorphism through edge contractions with an edge validity condition I know that graph contractability is $NP$-complete. To be specific given $G=(V_1,E_1)$ ...
4
votes
1answer
2k views

How to prove the NP-completeness of the ``Exact-3D-Matching`` problem by reducing the ``3-Partition`` problem to it?

Background: The Exact-3D-Matching problem is defined as follows (The definition is from Jeff's lecture note: Lecture 29: NP-Hard Problems. You can also refer to 3-...
4
votes
2answers
269 views

maximum flow with all or nothing through each edge

Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the ...
4
votes
3answers
523 views

Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar ...
4
votes
2answers
139 views

Showing a problem on a specific graph is NP-hard

Maybe there is a trivial answer to my question or maybe there is not any. But I ask it here and appreciate if anyone can give me a clear answer. We know that a set of problems like minimum clique ...
4
votes
1answer
73 views

Vertex cover with covering radius 2

Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices? A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
4
votes
1answer
215 views

Why are there no complete problems for NP ∩ coNP?

The fact that PPAD is a subclass of TFNP seems to be taken as evidence that PPAD cannot be shown complete (or hard) for classes of independent interest like NP ∩ coNP. Slightly confusing, it even ...
4
votes
1answer
462 views

Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?

Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted? That is, each node in the topological graph should be visited once at least (instead of exactly). Is ...
3
votes
1answer
163 views

NP-hardness of a scheduling problem

Problem: Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the time weight function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge $...
3
votes
2answers
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 ...
3
votes
2answers
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, ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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}. $$...
2
votes
2answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
1k views

How can I prove DP completeness?

We defined the class $\text{DP}$ like this: $$\text{DP} := \{ A \setminus B : A, B \in \text{NP} \}$$ We say a problem $P$ is $\text{DP}$ complete iff $P \in \text{DP}$ and $X \leq P \forall X \in \...
2
votes
1answer
94 views

Path in a vertex-weighted undirected graph

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$. Does ...
2
votes
1answer
160 views

Lower bounding the minimum equivalent graph

The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$. The minimum equivalent graph $G' = (...
2
votes
1answer
278 views

Minimum number of vertices to remove to bound the largest connected component of a graph

I have this problem, maybe anybody could help. Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G \...
2
votes
2answers
392 views

Direction of restriction for NP hard proves

I have a very silly question, as I am reading through all the proofs showing a problem is NP hard, one of the techniques is by showing an already-proven NP complete problem is a special case for that ...
1
vote
2answers
2k views

If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
1
vote
1answer
444 views

Set cover problem with sets of size 2

I have a question about the Set Cover problem: If I get a universe $U$, and $m$ subsets of size exactly $2$, and an integer $k$. Is this problem is still NP-C or I can solve it on a polynomial time? ...
1
vote
1answer
117 views

Sudoku Puzzles in O log n time although inefficient

Suppose, I got a hypothetical fixed list of all possible general Sudoku puzzles. I then create the pseudo-code to demonstrate the algorithm. The algorithm does a search to compare the indexes of ...
1
vote
1answer
704 views

If A is polynomial time reducible to B does that imply not(A) is polynomial reducible to not(B)

$A\leq_p B \iff \bar{A}\leq_p \bar{B}$ (if A is polynomial time reducible to B does that imply that complement of A is polynomial reducible to complement of B) I was told that this is the case based ...
1
vote
1answer
2k views

Prove Partition is NP-Complete using that SubsetSum so is it

The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete. The ...
1
vote
0answers
143 views

Saxe's proof of 1-embeddability

I've been reading Saxe's proof that 1-embeddability of integer weighted graphs is NP-Complete (http://www.math.columbia.edu/~dpt/RigidityREU/Saxe79EmbedNPHard.pdf Theorem 3.2). I don't understand how ...
1
vote
1answer
145 views

Quadratic Diophantine equation - Polynomial Time Cases

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$ a*x^2+b*y= c $$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete. The solution (x, y) are ...
1
vote
1answer
145 views

Show Resource Allocation Problem is NP-Complete

We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...
1
vote
1answer
112 views

Polynomial time reductions between two problems

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 $...
1
vote
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 ...
1
vote
0answers
248 views

Reducing a problem with two knapsack that needs equal number of items from Knapsack?

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