Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

187 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
18 votes
0 answers
546 views

Complexity of the densest $k$-subgraph problem on planar graphs

In the densest $k$-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is ...
Aaron Schild's user avatar
18 votes
1 answer
2k views

Complexity of interval cover problem

Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to ...
Torsten Mütze's user avatar
17 votes
0 answers
945 views

Deeper look at Algorithmica?

Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995. He presented five possible worlds we could be living in, depending on how P and NP were related. The ...
András Salamon's user avatar
17 votes
0 answers
430 views

Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?

I am interested in the following problem. Node Multiway Cut on Planar Graphs with terminals on the outer face Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals which ...
Bart Jansen's user avatar
  • 5,265
16 votes
0 answers
496 views

a geometric variant of k-medians. NP-hard or in P?

The following problem is a special case of k-medians. Is it NP-hard? Is it in P? Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$. Output: a set ...
Neal Young's user avatar
  • 10.1k
16 votes
0 answers
1k views

Phase Transitions in NP Hard Problems

SAT Problems have a phase transition that depends on the ratio $r$ of variables to clauses. Below $r$, SAT problems are solvable quickly; above, they become difficult. The same is true of NP ...
Ganesh's user avatar
  • 521
14 votes
0 answers
190 views

NP-Hardness of 4-cycle packing problem in complete bipartite digraph?

A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
Mengfan Ma's user avatar
14 votes
0 answers
685 views

Does solving matrix multiplication in quadratic time imply that SETH is false?

I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time. In other words, ...
Michael Wehar's user avatar
13 votes
0 answers
287 views

Which monotone DNFs are evasive?

A Boolean function $\phi$ on variables $X$ is evasive if every decision tree for $\phi$ has height $|X|$. In other words, for any strategy that picks variables of $X$ and asks for their value, an ...
a3nm's user avatar
  • 9,232
12 votes
0 answers
356 views

NP complete problem help

I'm currently trying to find a reduction to this problem: Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
Andres Fuentes's user avatar
12 votes
1 answer
604 views

Recent progress on the next-to-shortest-path problem for directed graphs?

In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem: Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be ...
user514014's user avatar
11 votes
0 answers
166 views

Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$

Suppose we have a graph $G$ with maximum degree $\Delta$. Deciding if $G$ can be colored with $\Delta$ colors is easy: Brooks' theorem says that this is always possible, unless $G$ is a clique or an ...
Michael Lampis's user avatar
11 votes
0 answers
342 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 $|...
Alexey Milovanov's user avatar
10 votes
0 answers
136 views

Is this problem on unambiguous DNFs hard?

Call a DNF formula $\varphi = \bigvee_{i=1}^n C_i$ unambiguous if for every $i\neq j$, $C_i \land C_j$ is unsatisfiable. In other words, the disjunct $C_i$ contains some literal $l$ and $C_j$ contains ...
M.Monet's user avatar
  • 1,327
10 votes
0 answers
137 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 ...
a3nm's user avatar
  • 9,232
9 votes
0 answers
157 views

Optimal bee swarm plots: NP-hard?

Bee swarm plots are a way of visualizing one-dimensional data sets, similar to box plots. The idea is that if there's not too many points (e.g. <300) we can just plot them along the $x$-axis with ...
Falk Hüffner's user avatar
9 votes
0 answers
377 views

Subset sum problem with at most one solution for any target

This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there. We first consider the search version of the subset sum problem: Given a set $S$ of ...
DreamConspiracy's user avatar
9 votes
0 answers
182 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 $...
Dmytro Taranovsky's user avatar
9 votes
0 answers
1k 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 ...
Michael Wehar's user avatar
9 votes
0 answers
358 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 (...
pimlu's user avatar
  • 91
9 votes
0 answers
278 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 $\...
Quanquan Liu's user avatar
8 votes
0 answers
230 views

NP-hardness of approximation for unconstrained submodular maximization

The problem of unconstrained submodular maximization can be phrased as follows: Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$. Here a ...
Yuval Filmus's user avatar
  • 14.4k
8 votes
0 answers
815 views

Is this minimization problem NP-Complete?

We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns. The problem is ...
RIchard Williams's user avatar
8 votes
0 answers
1k views

Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?

This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware. Informal ...
Tsuyoshi Ito's user avatar
  • 16.5k
7 votes
0 answers
245 views

How hard is PromiseFlowFree?

Playing more Flow Free, I think I've realized why I'm so amazingly brilliant at this game: The objective is to connect all pairs while covering the entire board, but in every puzzle there is always ...
domotorp's user avatar
  • 13.9k
7 votes
0 answers
514 views

On the shortest vector problem (is it $NP$-complete?)

Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum. Has this been derandomized?
Turbo's user avatar
  • 12.8k
7 votes
0 answers
166 views

What relations are there between a problem hardness and the hardness of verifying a witness?

I had some hard times trying to formulate the question, so I'll start with some examples: Suppose you are given a Dominating Set instance, $<G,k>$. Now suppose I give you a set of vertices $D$ ...
R B's user avatar
  • 9,448
7 votes
0 answers
573 views

Another Solution Problem (ASP) of integer multi-commodity flow: is it NP-complete?

I know that integer multicommodity flow is NP-complete. It was proven in On the complexity of time table and multi-commodity flow problems that any SAT problem can be reduced to an integer ...
user3340523's user avatar
7 votes
0 answers
168 views

Universal tractable problem solver

Consider $X$ an $\mathsf{NP}$-complete language e.g. $3-SAT$. I'm looking for an algorithm $A$ for solving $X$ with the following property. Given $M \subset \lbrace 0, 1 \rbrace^*$ any set of words s....
Vanessa's user avatar
  • 2,151
7 votes
0 answers
222 views

What is the complexity of pallet loading for identical non-rectangular objects?

In the pallet loading problem, we are asked to place a set of small identical 2-D rigid objects into a large bounding rectangle such that no two objects overlap. This problem is a special case of the ...
Adam Paetznick's user avatar
6 votes
0 answers
95 views

Certifying the promise in hard promise problems

Do we happen to know of any promise problems where the problem is both conditionally hard (say, NP-hard) while simultaneously being able to certify that the instance satisfies the given promise? For ...
Noel Arteche's user avatar
6 votes
0 answers
99 views

Cycle packing with degree condition

Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard? Without the degree condition, the ...
TZM's user avatar
  • 133
6 votes
0 answers
141 views

Computing Sequences with Addition Chains In pseudopolynomial time?

Computing Sequence $a_1, \ldots, a_n$ with addition chains (CSAC) is the problem of finding the shortest sequence $b_1, \ldots, b_m$ with the following properties: $b_1=1$. Every $b_i$ with $i>1$ ...
Alexey Milovanov's user avatar
6 votes
0 answers
191 views

An optimal subspace projection problem

Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that $$\...
Paul's user avatar
  • 271
6 votes
0 answers
293 views

Quantum computer versus Random 3-SAT?

It seems to be commonly believed that a quantum computer cannot efficiently solve NP-hard problems. What about problems that are challenging in the average-case, such as Planted Clique and Random 3-...
Minkov's user avatar
  • 842
6 votes
0 answers
852 views

Is this permutation-sum problem NP-complete?

A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular,...
Paolo Valente's user avatar
6 votes
0 answers
253 views

NP-hardness of tasks graph assignment to two heterogenous servers

I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated. Problem definition Given is a directed acyclic graph $G=(V,E)$ ...
marszall87's user avatar
6 votes
0 answers
143 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 ...
Roffle's user avatar
  • 81
6 votes
0 answers
216 views

Further question on hardness of node partitioning under shortest path constraint

This question first appeared at Hardness of node partitioning under shortest path constraint and I restate it here Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \...
Kid's user avatar
  • 283
5 votes
0 answers
107 views

Joint Scheduling Problem with Variables Arrival Times

The scheduling problem $1\bigl|r_j\bigl|\Sigma\,U_j$ is strongly NP-hard but when preemption is allowed the scheduling problem $1\bigl|pmtn,r_j\bigl|\Sigma\,U_j$ becomes strongly polynomial. I have a ...
zdm's user avatar
  • 325
5 votes
0 answers
146 views

An NP-hard Hidden Subgroup Problem

I've encountered a model which can be thought of as a version of the Hidden Subgroup Problem (https://en.wikipedia.org/wiki/Hidden_subgroup_problem), but that doesn't quite meet the standard problem's ...
Shaull's user avatar
  • 5,571
5 votes
0 answers
191 views

Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover

This problem came up in my study of digraphs: Given a connected bipartite graph $G = (A \cup B, E)$, a vertex cover is a set $S$ of vertices such that every edge has some endpoint in $S$. Note that $A$...
Karagounis Z's user avatar
5 votes
0 answers
86 views

Complexity of a specific class of definite integrals

INTRODUCTION: From the answer to this question I learned that deciding whether a definite integral is $0$ or not can be NP-complete, as the following integral representation of the Number Partition ...
Leonardo's user avatar
  • 181
5 votes
0 answers
211 views

Is monotone 1-in-3 MAXSAT known to be APX hard?

Monotone 1-in-3 SAT is the problem where each clause of the SAT problem contains exactly 3 positive variables. The goal is to find an assignment such that exactly one variable is true in each clause ...
karmanaut's user avatar
  • 1,177
5 votes
0 answers
87 views

Complexity of bounded degree full contraction

This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows: Instance: A graph $G$ and two integers $d$ and $k$. Question: Is there a ...
delete000's user avatar
  • 818
5 votes
0 answers
242 views

NP-completeness of a specific topological sorting problem

Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a ...
Ivan Smirnov's user avatar
5 votes
0 answers
125 views

Completing a matrix (over the reals) to be singular

Consider the following problem: you are given a matrix (say, with rational entries) some of whose entries are actually left blank; can these blanks be filled in with real numbers so that the resulting ...
P.T.'s user avatar
  • 51
5 votes
0 answers
715 views

NP-completeness of the Dominating set problem for planar graphs of maximum degree 3?

I am trying to learn about some techniques that are used for proving the NP-completeness of domination related problems. One of the problems that is known to be NP-complete is the domination number of ...
Elham Roshanbin's user avatar
5 votes
0 answers
122 views

Variation on block design/set cover

Given 3 parameters $s, r$ and $t$, where $r \leq t$, I want to construct $t$ sets such that each integer $\{1, \ldots, s\}$ appears in exactly $r$ of these sets. The question is: Is it possible to ...
ragip's user avatar
  • 51
5 votes
0 answers
2k 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 ...
assafisr's user avatar