Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
23
votes
2answers
3k views

Natural CLIQUE to k-Color reduction

There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. ...
3
votes
1answer
168 views

bounded outdegree bipartite spanners

Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties : $G'$ ...
30
votes
6answers
2k views

Is there a natural problem on the naturals that is NP-complete?

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
3
votes
1answer
404 views

Is this multiprocessor scheduling problem with overlaps NP-Hard?

The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the ...
16
votes
1answer
740 views

What is the complexity of rectangle packing when rotations are allowed?

In the rectangle packing problem, one is given a set of rectangles $\{r_1,\dots,r_n\}$ and bounding rectangle $R$. The task is to find a placement of $r_1,\ldots,r_n$ inside $R$ such that none of ...
6
votes
1answer
4k views

Guidelines to reduce general TSP to Triangle TSP

I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie: $D(a, b) \leq ...
1
vote
1answer
1k views

Vehicle routing problem over Manhattan distances

I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot. Is the following ...
5
votes
1answer
472 views

What if a problem is both in $\Pi_2^p$ and $NP$-hard?

If a problem $P$ belongs to both $\Pi_2^p$ and $NP$-hard (thanks to some reduction from a $NP$-complete problem) but not to $NP$, does it imply that $P$ is $\Pi_2^p$-complete? If the answer is no, ...
19
votes
2answers
913 views

Is feedback vertex set problem is solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set is NP-complete for general graphs. It is known to be NP-complete for degree-8 bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is poly-time ...
8
votes
1answer
277 views

NP-hardness of a Set Cover specialization

Is the following problem NP-hard? Given a set of $N$ real numbers (targets) $x_1,\dotsc,x_N$ and a "trident" defined by two distances $a$, $b$ from the center of the trident, what is the minimum ...
10
votes
2answers
7k views

Is the N Queens problem NP-hard?

The N-queen problem is this: Input : N Output : A placement of N "queens" on an NXN chessboard such that no two queens lie on the same row, column or diagonal. Doing a google search on this, I ...
-5
votes
1answer
537 views

Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
4
votes
3answers
8k views

what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSR in the form of VRP ...
5
votes
0answers
978 views

Bounded Post Correspondence Problem NP-Complete Proof

I'm looking for a simple proof that shows that the Bounded-PCP problem belongs to NP-Complete as many text books say so. It is clear to me that the problem is decidable but I cannot find any reduction ...
2
votes
1answer
756 views

Is “meeting/room planning” NP-complete?

Short summary: The problem is to assign people to meetings at different days while respecting the capacities and (inter-day) constraints of the meetings. Each person can only attend at most one ...
6
votes
0answers
139 views

Complexity of DTMC subsystems

A discrete-time Markov chain (DTMC) is a tuple $M=(S,s_{init},P)$ where $S$ is a finite set of states, $s_{init}\in S$ the initial state, and $P:S\times S\to[0,1]$ the one-step transition probability ...
15
votes
1answer
1k views

Is the following problem NP hard?

Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer. The goal is to find ...
1
vote
2answers
2k views

Bin packing approximation with different bin sizes

Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size? More formally, there are $n$ bins of size $b_i$ for $i=1,\dotsc,n$, and $m$ ...
11
votes
2answers
341 views

Is the problem of finding operators to satisfy a list of boolean variables NP complete?

This is similar to SAT, except that we know the assignment of each variable, but do not know the assignment of any boolean operator. In that case, is finding the assignment of each operator so the ...
4
votes
3answers
476 views

bin packing with overlapping objects

I have $N$ bins with capacity $M$ and $k$ objects with size $s_i$. The goal is to pack these objects in the bins. Until now it is similar to the bin-packing problem. But the twist is that each object ...
5
votes
0answers
182 views

Reduction from planar bounded NCL to a static puzzle game

I call Fill3 the following simple game: the input is a $n \times n$ grid; every cell of the grid has a type: OR, AND, CHOICE, FANOUT and FIXED and can be rotated 0,...
8
votes
1answer
792 views

Interesting SUBSET-SUM problems

I know the following variants of SUBSETSUM problems: $ \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} $ (Elberfeld at. al., 2010), NP-complete $ \mathtt{SUBSETSUM} $, and NEXP-complete $ \mathtt{...
15
votes
1answer
338 views

Two matrices related by a permutation $B = P A P^T$ - complexity

What is computational complexity of the following problem: given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$ If it helps, one ...
2
votes
3answers
969 views

Complexity of Portal 2

I am studying the complexity of Portal 2 and I would like to know if the problem has been studied before. In particular, I would be interested any reference discussing the complexity of Portal 2 and ...
7
votes
2answers
333 views

What is known about the H-factor problem?

Background The $\mathcal{H}$-factor problem (a.k.a. the degree prescribed factor problem, or the degree prescribed subgraph problem) is defined as follows: Given a graph $G=(V,E)$ and a set $H_v \...
2
votes
0answers
247 views

Help with an np-completeness proof [closed]

I know that graph contractability is NP-complete: given $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? Consider the following ...
-3
votes
1answer
311 views

What is meant by “if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP”?

For example, for the $k$-center problem we want to prove that a 2-approximation algorithm is optimal. A proof is presented on page 39 (Theorem 2.4) in Williamson and Shmoys, The Design of ...
3
votes
0answers
147 views

Partitioning the vertices of a complete graph with weights on both vertices and edges with constraints

Given the complete graph on n vertices. Each vertex and each edge has a positive weight associated with it. What is desired is to partition the vertices into parts so that the sum of the weights of ...
3
votes
1answer
412 views

Do you know this problem of deciding whether a given 0-1 matrix contains k pairwise disjoint “column-paths”?

Problem: $X$ Instance: A $m\times n$ 0-1 Matrix $A$, $k \in \mathbb{N}$. Question: Does $A$ contain $k$ pairwise disjoint "column-paths"? A column-path starts in the first column, ends in the ...
7
votes
1answer
425 views

Techniques for proving NP completeness for a specific sequence of instances

Most NP-completeness proofs I have seen pertain to proving that a problem on a class of instances is NP-complete. E.g., satisfiability is NP-complete on the class of instances with clauses having ...
8
votes
3answers
743 views

Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

There are some NP-Complete problems ($ \mathsf{SAT} $, $ \mathsf{SUBSETSUM} $, etc.) known to be in $ \mathsf{DSPACE(n)} $. What about the sub-linear spaces? Is there any known NP-Complete (or NP-...
13
votes
4answers
504 views

Problems with complexity between P and NP that have NP-complete generalizations

Can anyone list some well-known problems that satisfies the following conditions: ...
12
votes
4answers
1k views

Is the feedback vertex set problem on planar bounded degree graphs hard?

Is it known whether the feedback vertex set problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?
20
votes
1answer
560 views

Minimum chordless odd-cycle graph completion: is it NP-hard?

The following interesting problem came up in my research recently: INSTANCE: Graph $G(V, E)$. SOLUTION: A chordless odd-cycle completion, defined as a superset $E'$ of the edge set $E$ so that ...
1
vote
1answer
268 views

Is the following optimization problem (another variant to a previous problem) NP-hard?

This problem is a following up question on this one. The only difference is the addition of $3^{rd}$ constraint "$\sum_{i} x_{ij} \le M$", where M is a constant number. This constraint essentially ...
2
votes
1answer
184 views

What is the known complexity of this game? (similar to PushPush-1)

I've been looking at a few entries in http://library.msri.org/books/Book56/files/10demaine.pdf (on combinatorial algorithmic game theory). I didn't see the following game listed there, and I want to ...
3
votes
1answer
203 views

Is the following optimization problem (a variant to a previous problem) NP-hard?

This problem is a following up question on this one. The only difference is the newly added constraint in the bold font. Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \...
1
vote
0answers
296 views

NP-Completeness of Certain Bounded Degree Graphs [closed]

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) Is the set of all (G, k) where G is a graph ...
2
votes
2answers
474 views

Is the following optimization problem NP-hard?

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight $w_{...
11
votes
1answer
409 views

3-Clique Partition for graphs of fixed diameter

The 3-Clique Partition problem is the problem of determining whether the vertices of a graph, say $G$, can be partitioned into 3 cliques. This problem is NP-hard by a simple reduction from the 3-...
8
votes
1answer
2k views

What are good approximation algorithms for the subset sum problem so far?

By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.
7
votes
1answer
462 views

NEXP Cook-Levin

I've come across the following lemma (without proof): The first part of the lemma states that for any $x$, there's a 3CNF exponential Boolean formula $f(x)$ that is satisfiable if and only if $x \in ...
10
votes
1answer
278 views

Hamilton Decomposition Decision Problem

Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a Hamilton decomposition of $G$ if the subgraph induced by each set $V_i$ is either a Hamilton graph ...
3
votes
1answer
575 views

Simplest proof of NP-completeness

The only first-principles "proof" that a problem is NP-complete I encountered is from Introduction to algorithms, and deals with the circuit-satisfiability problem. According to the authors, many ...
6
votes
1answer
219 views

NP-completeness of a problem using a “T-gadget”

Working on a problem I came up with the following "T-gadget": It has 3 connectors (A, B, C); each connector has two wires (A1,A2; B1,B2; C1,C2); it can be rotated (0, 90, 180, 270 degrees); two ...
13
votes
3answers
499 views

Is this optimum travelling problem under deadlines NP-hard on trees?

One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. Is there any reference for it? Problem: There is a tree $T(V,E)$, each edge has symmetric ...
3
votes
1answer
300 views

reduction of maximum independet set to minimum distance of code

Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity ...
-1
votes
2answers
753 views

What progress has been made to prove whether or not p=np? [closed]

I know that it is still one of the biggest mysteries of computer science whether non-deterministically polynomial problems can be solved in polynomial time. I am curious to know what makes this ...
18
votes
4answers
2k views

Implications of unprovability of $P\neq NP$

I was reading "Is P Versus NP Formally Independent?" but I got puzzled. It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is not ...
3
votes
1answer
393 views

Approximate bound/algorithm for “product of sums maximization” problem

I am looking for some approximate algorithm with upper/lower bound for the following problem: Given a set of positive integers $\{a_1, a_2, \dots, a_n\}$, partition $\{1, 2, \dots, n\}$ into disjoint ...