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
-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
449 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
644 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
3answers
6k 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 ...
5
votes
1answer
241 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
3answers
1k 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), ...
5
votes
1answer
802 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?
4
votes
1answer
460 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 ...
4
votes
1answer
926 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-...
4
votes
0answers
169 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
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
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
190 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
2answers
138 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
3answers
505 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
1answer
211 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
65 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 ...
3
votes
1answer
549 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
86 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 ...
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
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
504 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
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 ...
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
93 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
2answers
108 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
380 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 ...
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
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
1answer
159 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
275 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 \...
1
vote
1answer
77 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
98 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
88 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 ...
1
vote
1answer
139 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
0answers
141 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
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
50 views

Partitioning in time complexity of the sum

We all know the partitioning problem: Given a super-set S of integers, can we partition S into 2 subsets with the same sum. And of course this problem is NP-complete. My question is - let's denote M ...
1
vote
1answer
423 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
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
2answers
148 views

XOR of two NP-Complete languages

Given two NP-Complete languages A and B, show that the language: $L = A\bigoplus B =\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\}$ is not necessarily NP-Complete. Remember $a\bigoplus b$ when $|...
1
vote
2answers
608 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
1answer
111 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
1answer
622 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
245 views

Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones

select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones
1
vote
3answers
282 views

Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
1
vote
1answer
1k views

Set cover problem and the existence of such cover

In the set cover problem we want to find in the $\mathbb{S} \subset 2^\mathbb{U}$ the subset $\{s_i\}_{1..k}$, such that $\cup s_i = \mathbb{U}$ for given $K$, where $k \le K$. But how to reduce the ...
1
vote
0answers
236 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 ...