Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

151 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
18
votes
0answers
530 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 ...
18
votes
1answer
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 ...
17
votes
0answers
825 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 ...
16
votes
0answers
438 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 ...
16
votes
0answers
378 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 ...
15
votes
0answers
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 ...
14
votes
0answers
169 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 ...
14
votes
0answers
633 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, ...
13
votes
0answers
241 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 ...
12
votes
0answers
346 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 ...
11
votes
0answers
324 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 $|...
10
votes
1answer
333 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 vertices in ...
10
votes
0answers
128 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
150 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 ...
9
votes
0answers
170 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
550 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
350 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
260 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
0answers
312 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 ...
8
votes
0answers
212 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 ...
8
votes
0answers
801 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 ...
8
votes
0answers
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 ...
7
votes
0answers
227 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 ...
7
votes
0answers
445 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?
7
votes
0answers
163 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$ ...
7
votes
0answers
558 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 ...
7
votes
0answers
166 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....
7
votes
0answers
205 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 ...
6
votes
0answers
167 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 $$\...
6
votes
0answers
787 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
0answers
252 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)$ ...
6
votes
0answers
142 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 ...
6
votes
0answers
210 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) \...
5
votes
0answers
171 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$...
5
votes
0answers
80 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 ...
5
votes
0answers
139 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 ...
5
votes
0answers
81 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 ...
5
votes
0answers
201 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 ...
5
votes
0answers
124 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 ...
5
votes
0answers
654 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
0answers
120 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 ...
5
votes
0answers
1k 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 ...
5
votes
0answers
223 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,...
4
votes
0answers
89 views

Analogue of Chow-Liu tree for $L_1$

Say $\Omega$ is a finite set and $f$ a probability mass function (pmf) over $\Omega^d$. Now let $T$ be a spanning tree on the set $V=\{1,2,\ldots,d\}$, and consider a collection of one- and two- ...
4
votes
0answers
127 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 ...
4
votes
0answers
87 views

Inverting Kronecker product on vectors is in P?

Problem: Given a vector V of positive integers, find two vectors v1 and v2 such that the Kronecker product of v1 and v2 is equal to p(V) (where p(V) is a suitable permutation of V). Example: Input: V={...
4
votes
0answers
174 views

A variant of hitting set: finding a matching to hit all edge sets

In general, the hitting set problem is given a family $\cal S$ of sub-sets, $\{S_1, \cdots, S_h\}$, and a universal set $U = \bigcup_{i\in [1,h]} S_i$. It asks for a minimum set $H \subseteq U$ ...
4
votes
0answers
140 views

min weight k-closure on DAG

The problem Given a (connected) DAG $G(V,E)$ where each node is assigned an (non-negative) integer weight an integer k where $0\leq k\leq|V|$ Find a induced subgraph $H$ of $G$ consisting of $k$ ...
4
votes
0answers
175 views

Random self reducibility and NP

I was reading the Wikipedia page Random self-reducibility and it states: If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$. I am ...
4
votes
0answers
289 views

Computational Complexity of cycle double cover

Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...