Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
187
questions with no upvoted or accepted answers
18
votes
0
answers
548
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 ...
- 367
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 ...
- 181
17
votes
0
answers
953
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 ...
- 19k
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 ...
- 5,265
16
votes
0
answers
500
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 ...
- 10.8k
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 ...
- 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 ...
- 513
14
votes
0
answers
688
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, ...
- 5,127
13
votes
0
answers
628
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 ...
- 231
13
votes
0
answers
289
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 ...
- 9,269
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 ...
- 121
11
votes
0
answers
170
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 ...
- 3,698
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 $|...
- 2,003
10
votes
0
answers
147
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 ...
- 1,429
10
votes
0
answers
138
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,269
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 ...
- 1,023
9
votes
0
answers
378
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 ...
- 191
9
votes
0
answers
183
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 $...
- 2,577
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 ...
- 5,127
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 (...
- 91
9
votes
0
answers
280
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 $\...
- 313
8
votes
0
answers
232
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 ...
- 14.5k
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 ...
- 189
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 ...
- 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 ...
- 14k
7
votes
0
answers
517
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?
- 12.9k
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$ ...
- 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 ...
- 71
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....
- 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 ...
- 640
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 ...
- 988
6
votes
0
answers
102
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 ...
- 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$ ...
- 2,003
6
votes
0
answers
192
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
$$\...
- 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-...
- 852
6
votes
0
answers
853
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,...
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)$ ...
- 239
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 ...
- 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) \...
- 283
5
votes
0
answers
152
views
Complexity of numerical 3-dimensional matching where the three multisets are identical
Consider the following problem:
Input: one multiset $S = \{s_1, \ldots, s_n\}$ of positive integers written in unary
Output: can we build $n$ triples that sum to the same value, using each element of ...
- 9,269
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 ...
- 325
5
votes
0
answers
148
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 ...
- 5,626
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$...
- 607
5
votes
0
answers
87
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 ...
- 181
5
votes
0
answers
225
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 ...
- 1,177
5
votes
0
answers
88
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 ...
- 818
5
votes
0
answers
243
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 ...
- 191
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 ...
- 51
5
votes
0
answers
718
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 ...
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 ...
- 51