The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
10
votes
2answers
576 views

Exact exponential-time algorithms for 0-1 programming

Are there known algorithms for the following problem that beat the naive algorithm? Input: A system $Ax \le b$ of $m$ linear inequalities. Output: A feasible solution $x^*\in \{0,1 \}^n$ if ...
10
votes
1answer
624 views

Probability of generating a desired permutation by random swaps

I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list $L=...
10
votes
2answers
1k views

NP-complete variants of undecidable problems?

Examples of bounded $NP$-complete variants of undecidable sets: Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps} Bounded Tiling={ $(T, 1^t)$| there is ...
10
votes
1answer
863 views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
10
votes
2answers
501 views

Complexity of hidden polygon puzzle on square grids?

Hiroimono is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle. The problem is: Input: Given a set of points on on a $n$x$n$ square grid and ...
10
votes
1answer
295 views

How hard is deciding the existence of Red-Blue perfect matching?

Two-colorable perfect matching problem is to decide whether a graph has coloring with two colors such that each node has exactly one neighbor the same color as itself. The problem was proven to be NP-...
10
votes
1answer
3k views

Monotone bijections between lists of intervals

I have the following problem: Input: two sets of intervals $S$ and $T$ (all endpoints are integers). Query: is there a monotone bijection $f:S \to T$? The bijection is monotone w.r.t. the set ...
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 ...
10
votes
1answer
401 views

What are the complexities of the following SAT subsets ?

Assume $P \neq NP$ Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$). |x| is the size of the instance x. Let L be ...
10
votes
1answer
417 views

Hardness of constrained star system problem?

A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-...
10
votes
2answers
219 views

Common insights into hypothetical complexity of graph problems

I came across two examples of hypothetical hardness of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. ...
10
votes
2answers
920 views

A variant of Critical SAT in DP

A language $L$ is in the class $DP$ iff there are two languages $L1 \in NP$ and $L2 \in coNP$ such that $L = L1 \cap L2$ A canonical $DP$-complete problem is SAT-UNSAT : given two 3-CNF expressions, $...
10
votes
2answers
684 views

Set optimization problem - is it np-complete?

Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective ...
9
votes
3answers
762 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-...
9
votes
1answer
849 views

Does every Turing-recognizable undecidable language have a NP-complete subset?

Does every Turing-recognizable undecidable language have a NP-complete subset? The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
9
votes
3answers
397 views

Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

Problem statement : Let $M$ be a (potentially nondeterministic) pushdown automaton and let $\cal A$ be its input alphabet. Is there a word $w \in \cal A^*$ s. t. $|w| \leq k$ that is accepted by $M$ ?...
9
votes
1answer
348 views

Is the backup problem NP-complete?

Is the following decision problem NP-complete: Let $G$ be an undirected graph and $b \le c$ two integers. Is it possible to select for every vertex of $G$ exactly $b$ different neighbors ...
9
votes
1answer
673 views

Proof that sparsest cut is NP-hard

Everywhere that I read about the sparsest cut problem, it only says that the problem is known to be NP-hard. Where can I find a proof of this? Which known NP-hard problem reduces to the sparsest cut ...
9
votes
2answers
373 views

Exact exponential-time algorithms for 0-1 programs with nonnegative data

Are there known algorithms for the following problem that beat the naive algorithm? Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers. Output: an ...
9
votes
3answers
689 views

Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

Suppose P != NP. We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there ...
9
votes
1answer
145 views

Best known asymptotic PCP sizes / 3-SAT

What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am ...
9
votes
1answer
675 views

NP-Hardness of a special case of orthogonal packing problem

Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used ...
9
votes
1answer
227 views

Complexity of digraph homomorphism to an oriented cycle

Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to $...
9
votes
1answer
194 views

What is known about the hardness of the chromatic index for restricted graph classes?

There is a nice paper from 1991 that contains three diagrams about different graphclass-families showing what is known about the hardness of determining the chromatic index for them. Are there any ...
9
votes
1answer
453 views

Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?

The standard problem 1-in-3 SAT (or XSAT or X3SAT) is: Instance: a CNF formula with every clause containing exactly 3 literals Question: is there a satisfying assignment setting precisely 1 literal ...
9
votes
1answer
1k views

Complexity of finding the maximal number of pair-wise disjoint sets

Assume that I have $P$ sets with elements taken from $r$ possible ones. Each set is of size $n$ ($n<r$), where the sets can overlap. I want to determine whether the following two problems are NP-...
9
votes
1answer
157 views

Edge-partitioning into rainbow triangles

I'm wondering if the following problem is NP-hard. Input: $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,2,3\}$ of the edges ($f$ does not verify any specific property). Question:...
9
votes
1answer
265 views

Maximum weight “fair” matching

I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching". Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that ...
9
votes
0answers
139 views

Is unary $\Pi_2$-SUBSETSUM coNP-complete?

Consider the following problem: for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation define is it true that for every $S \subseteq \{1, ..., 2n \}$ such that $|...
9
votes
0answers
126 views

Complexity of fractional SAT

Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
9
votes
0answers
307 views

What are the best known reductions from SAT to CNF-SAT?

Problems Let SAT denote the following problem: Given a boolean formula, does there exist a satisfying assignment? Let CNF-SAT denote the following problem: Given a ...
9
votes
0answers
308 views

Triangle arrangement problem

Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
9
votes
0answers
117 views

Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
9
votes
0answers
241 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of $\...
8
votes
3answers
3k views

Is Deolalikar's 2010 proof that $P \ne NP$ correct?

There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof. So ... is the proof correct or not ? (Please only answer this if you ...
8
votes
3answers
1k views

P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
8
votes
4answers
2k views

Complexity of marriage matching problem?

Suppose you have $n$ males and $n$ females. Each person has $m$ attributes. Each person indicates a set of attributes that a possible candidate should have. A matching is a set of pairs. Each pair ...
8
votes
2answers
358 views

Complexity of the $(3,2)_s$ SAT problem?

Let define the $(3,2)_s$ SAT problem : Given $F_3$, a satisfiable 3-CNF formula, and $F_2$, a 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable? What ...
8
votes
1answer
650 views

What is complexity of this max-edge subgraph problem?

While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below: Given a connected undirected graph, finding a maximum-...
8
votes
1answer
425 views

Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
8
votes
1answer
624 views

Minimum Triangle Covers

Given a graph $G$, what is the minimum number of edges of $G$ that we need to delete to make the graph triangle free? To my untrained eye, this appears to be a difficult problem. Is this problem ...
8
votes
3answers
366 views

A partition problem in which some numbers may be cut

In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard. However,...
8
votes
1answer
254 views

NP-hardness on Cayley graphs

What is known about complexity of NP-hard problems on Cayley graphs? Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ...
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.
8
votes
1answer
549 views

Fitting minimum number of rectangles of width/height 1 into a 2D grid

Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied and you need to put the minimum number of non-overlapping rectangles of any size w x h where ...
8
votes
1answer
374 views

NP-hardness of an optimization problem

While studying a problem in algorithmic game theory I got interested in the complexity of the following optimization question: Problem Given: ground set $U = [n] = \{1,\ldots,n\}$ given by $n$, $...
8
votes
1answer
337 views

NP-hardness proof: looking for some good restricted np-hard problems

To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can ...
8
votes
1answer
313 views

On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not ...
8
votes
1answer
200 views

A partition problem with order constraints

In the OrderedPartition problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$. The output is a partition of the ...
8
votes
1answer
623 views

Is that particular case of the “minimum weight solution to linear equations” still NP-complete?

We in our research group are working in the application of heuristic methods to the inverse illumination problem (that is, given a set of constraints about the illumination conditions in a scene, find ...