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
445 views

Proving that finding wheel subgraphs is NP-complete

Can you help me with this problem ? Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ ...
1
vote
1answer
1k views

Reduction from PARTITION to 3PARTITION

I'm considering the problem (a variant of 3-PARTITION, see here) with description Instance: Set of positive integers $A={w_{1},...,w_{n}}$ with $S(A)=\sum\limits_{i=1}^{n}w_{i} = 3m$. ...
0
votes
1answer
980 views

Reducing from Hamiltonian Cycle problem to the Graph Wheel problem [duplicate]

EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this ...
5
votes
1answer
642 views

NP-completeness of graph isomorphism through edge contractions with an edge validity condition

Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
4
votes
2answers
105 views

Karp hardness of searching for a matching cut

Follow-up question in the series: Karp hardness of searching for a matching erosion Karp hardness of searching for a matching split Maximum Matching Cut problem Input: An undirected graph $G(V, E)$ ...
3
votes
1answer
39 views

Karp hardness of searching for a matching erosion

First, read the previous question: Karp hardness of searching for a matching cut As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
3
votes
1answer
76 views

Karp hardness of searching for a matching split

UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
2
votes
1answer
68 views

Karp hardness of an equidistant vertex set

What is the hardness of the following problem? Input: An undirected graph $G(V, E)$ and a natural number $k$ Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO $\...
2
votes
1answer
4k views

Reducing from Hamiltonian Cycle to Subgraph Isomorphism

I am reading Subgraph isomorphism problem I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article. ...
2
votes
1answer
154 views

Topological sorting and NP-hard proof

I meet a problem. I can find a sub-optimal solution, but cannot find an optimal one and cannot prove its NPC hardness. The problem can also be described as follows. Given a sequence $X=\{x_1,x_2,...,...
1
vote
1answer
140 views

NP-Complete problem proof

I have an exam in two days and I am not sure if I have understood correctly the way of proving np-completness and how to pick a known np-hard problem to reduce it. Bellow I present a problem which I ...
1
vote
1answer
275 views

Subset sum to 0/1 knapsack

How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
0
votes
1answer
1k views

Decision Problem vs. Optimization Problem [duplicate]

Is the following statement correct? If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.
0
votes
1answer
49 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 ...
0
votes
1answer
443 views

Is the weighted transitive reduction problem NP-hard?

The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$. When $E^t \subseteq E$ it is NP-complete. ...
64
votes
7answers
15k views

Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
34
votes
4answers
24k views

Are there NP problems, not in P and not NP Complete?

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but ...
8
votes
2answers
12k views

are NP Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. ...
26
votes
2answers
9k views

Rule of thumb to know if a problem could be NP-complete

This question was inspired by a comment on StackOverflow. Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like ...
13
votes
2answers
20k views

Proving DOUBLE-SAT is NP-complete

The well known SAT problem is defined here for reference sake. The DOUBLE-SAT problem is defined as $\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least two ...
15
votes
1answer
613 views

Grid covering by rectangles

We have a $N_1 \times N_2$ grid. We have a collection of rectangles on this grid, each rectangle can be represented as a $N_1$-by-$N_2$ binary matrix $R$. We want to cover the grid with those ...
23
votes
2answers
5k views

NP completeness proof of a spanning tree problem

I am looking for some hints in a question asked by my instructor. So I just figured out this decision problem is $\sf{NP\text{-}complete}$: In a graph $G$, is there a spanning tree in $G$ that ...
20
votes
3answers
12k views

HALF CLIQUE - NP Complete Problem

Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please. With that said, here is the problem I am looking at: Let HALF-...
12
votes
3answers
2k views

Is 2-SAT with XOR-relations NP-complete?

I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination? Example Input: 2-SAT part: ...
12
votes
2answers
3k views

Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially ...
6
votes
1answer
457 views

How to prove that finding math proofs is $\text{NP}$-hard?

This is Exercise 2.11 of the book "Computational Complexity: A Modern Approach" by Arora and Barak. Mathematics can be axiomatized using for example the Zermelo-Frankel system, which has a ...
5
votes
1answer
2k views

What do we know about $NP \cap co-NP$?

What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it? (beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to ...
14
votes
2answers
2k views

Reduction from 3-Partition problem to Balanced Partition problem

The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks ...
7
votes
4answers
3k views

How are all NP Complete problems similar?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified ...
6
votes
4answers
4k views

What is an instance of NP complete problem?

I don't understand this definition of an "instance" of a problem. Quoting from the CLRS book on page 1054 on abstract problems (Chapter 34.1): We define an abstract problem $Q$ to be a binary ...
6
votes
1answer
259 views

Complexity of deciding the satisfiability of a quasi-monotone CNF formula

A quasi-monotone CNF formula is a formula where each variable appears at most once as a positive literal (and any number of times as a negative literal). What is the complexity of deciding its ...
5
votes
0answers
122 views

research on OR and AND compression in SAT formulas [closed]

this is a new/advanced paper on OR and AND compression of SAT formulas, a newer area of research that seems not covered in any textbooks so far. A simple proof that AND-compression of NP-complete ...
6
votes
1answer
2k views

Reducing directed hamiltonian cycle to graph coloring

The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring ...
6
votes
3answers
7k views

NP-completeness: Reduce to or reduce from?

Very simple question, but a mistake I make often enough that I'd love to have a standard reference. I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve $...
5
votes
1answer
7k views

Reduction from set cover problem to vertex cover problem

Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I ...
4
votes
2answers
769 views

Hardness proof of EVEN-ODD PARTITION

The PARTITION problem is NP-complete: INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$ QUESTION: Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = \...
4
votes
1answer
3k views

Proof that bin packing is strongly NP-complete?

Wikipedia claims that bin packing is strongly NP-complete. Unfortunately I haven't been able to find a proof. Does anyone know where to find it?
4
votes
1answer
86 views

Is GAP NP-hard with at most two balls per bins?

The generalized assignment problem (GAP) [1] is given by: Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and ...
3
votes
1answer
2k views

Why is the reduction from Vertex-Cover to Subset-Sum of polynomial time?

In the standard proof why Subset-Sum is (weakly) NP-complete, one reduces Vertex Cover to Subset-Sum by using suitable numbers with O(m+n) bits (where m is the number of edges and n the number of ...
3
votes
1answer
137 views

Solving a variant of the Exact cover problem

I am trying to solve a variant of the Exact cover problem where every element has to be covered exactly twice instead of once ( i.e. has to be in exactly two sets that are part of the cover). Now, it ...
3
votes
3answers
10k views

Prove that Hitting Set is NP-Complete

The Hitting Set Problem (HS) is defined as follow. Let $(C,k$) $C = \{ S_1, S_2, ..., S_m \}$ collection of subset of S i.e. $ S_i \subseteq S , \forall i$ $k \in \mathbb{N}$ We want to know if ...
1
vote
1answer
142 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 ...
1
vote
1answer
3k views

Proving that a problem is in NP

I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The ...
0
votes
1answer
6k 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
0answers
32 views

Partition a multiset into pairs that sum up to given numbers?

Given a multiset of $2m$ positive numbers, $S=\{s_1,s_2,\ldots,s_{2m}\}$ and given $m$ targets $t_1,t_2,\ldots,t_m$. Can we partition $S$ into $m$ pairs $(a_i,b_i)$ such that $a_i+b_i=t_i$, where $a_i\...
14
votes
1answer
2k views

Is it proven that quantum computation is no better at solving NP complete problems than classical computation?

Is it proven that quantum computation is no better at solving NP complete problems than classical computation or it's just believed?
7
votes
2answers
967 views

Polytime algorithm for SUBSET-SUM assuming P=NP

In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in ...
6
votes
6answers
3k views

Can a subset of an NP-complete problem be in P?

The problem is NP-complete (proven) for all input data (without exception). We assume that P != NP. Is it possible that there is an (infinitely large) subset of the problem, for which this subset is ...
6
votes
2answers
6k views

What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
6
votes
2answers
822 views

Example for a non-trivial PCP verifier for an NP-complete problem

During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating $\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$. I understand the ...