Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
732
questions
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
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 ...
- 51
5
votes
0
answers
276
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,...
- 23k
4
votes
1
answer
1k
views
If BQP contains NP, does this mean that P=NP?
There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that ...
- 51
4
votes
4
answers
4k
views
Why is P vs. NP so hard? [closed]
Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important?
Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem?
Why is it so hard?
All I'm looking for is the hindrances ...
- 175
4
votes
2
answers
252
views
Partition graph into 2 or more claw-free subgraphs
Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?
4
votes
3
answers
287
views
A Travelling Salesman variant where the next distance depends on distance travelled so far
The travelling salesman problem can be seen as a problem of selecting a permutation on $\{1,\ldots,n\}$ of minimun length, where the length of a permutation $\sigma$ is determined by pairwise ...
- 2,222
4
votes
1
answer
1k
views
Does P = NP imply NP being a strict subset of PSPACE? [closed]
Does $\textbf{P} = \textbf {NP}$ imply that $\textbf{NP} \subsetneq \textbf{PSPACE}$? Or, for a slightly stronger result, does it imply that $\textbf{NL} = \textbf P$?
- 143
4
votes
2
answers
976
views
For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?
The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows:
Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$.
Question: Does there exist $k$-...
- 9,448
4
votes
1
answer
250
views
Complexity reductions to Hamiltonian Path?
I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path.
Do ...
- 143
4
votes
2
answers
581
views
Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$
Since every $3$-SAT instance with $n$ variables can be expressed as a degree-$3$ polynomial over $\mathbb{F}_2$ with $n$ unknowns, the NP-hardness of $3$-SAT directly translates to NP-hardness of ...
- 791
4
votes
1
answer
3k
views
The significance of NP-Hard Problems in Cryptography
I didn't refer any literature but thought this was ideal to get views from people here..
Assuming that P=NP is proved would cryptography(only provable security) be impossible? Since the adversary can ...
- 269
4
votes
1
answer
501
views
Proof that the graph optimization problem is NP-hard
I'm trying to prove that the following optimization problem is NP-hard:
Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)...
- 239
4
votes
1
answer
289
views
Is SAT with two "opposite" solutions NP-hard?
Here is a variant of the SAT problem in which a satisfying assignment must have additional properties.
Input: A 3-CNF formula $f$ with variables $x_{1\dots k}$.
Output:
For an assignment $S$ of $x_{1\...
- 627
4
votes
1
answer
246
views
Chromatic number of a particular graph
Assume I have a parametrized graph. The parameters are two integers $x$ and $y<x$.
Let $S(x)=\{1, \ldots, x\}$.
The vertices of the graph are all the subsets of $S(x)$ of size $y$. Two vertices ...
- 43
4
votes
1
answer
196
views
Is there any relationship of hardness between the two problems?
Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D.
Consider the problem P1: With D as input, computes $(x^*,y^*)=argmax_{(x,y)}F(x,y|D)$ where x and y ...
- 119
4
votes
1
answer
546
views
Better approximation for special case of 3-hitting set
I have a question based on 3-Hitting Set problem. In this problem, we are given a universal set U of size n and a set of subsets S such that $\forall $ s $\in$ S |s|<=3.
FOr this problem, Integer ...
- 467
4
votes
2
answers
516
views
NP-hard problem which is easy on average
I have a feeling like I read somewhere that the Hamiltonian circuit problem is NP-hard, but it is easy on average, or easy for a random instance. However, I cannot find a reference for that, nor an ...
- 181
4
votes
1
answer
281
views
3-SAT mixed with 2-SAT formulas
Context: Refering to the question: Complexity of the $(3,2)_s$ SAT problem? and since the paper by Porshen and Speckenmayer : Satisfiability of mixed Horn formulas, we know that even when $F_3$ is ...
- 1,117
4
votes
1
answer
369
views
Balanced Max-2-SAT NP-Hardness
The Balanced Max-2-SAT is a special case of Max-2-SAT (each clause is a disjunction of exactly 2 literals) in which for every variable $x$, there is a $k$ such that $x$ appears positive exactly $k$ ...
- 312
4
votes
1
answer
177
views
Hardness of finding if a vertex lies on a simple directed path between two vertices
Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$?
I found a couple of hardness ...
- 241
4
votes
1
answer
298
views
Inapproximability of $(\alpha, \beta)$ bi-criteria approximation
An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$...
- 456
4
votes
2
answers
815
views
Stable Marriage with incomplete lists and ties - NP-hardness
According to [1] finding a weakly stable matching in a stable marriage (or SM) instance with incomplete lists and ties is NP-Hard.
According to [2] a weakly stable matching in a hospital-residents (...
- 343
4
votes
2
answers
558
views
NP-complete variants of NPI problems
Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
- 20.9k
4
votes
1
answer
237
views
Complexity of relaxed edge colouring
A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are ...
- 1,733
4
votes
2
answers
697
views
Graph coloring/partitioning problem
I'm interested in the complexity of the following problem:
Problem $P$: Given an undirected planar graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, ...
- 91
4
votes
1
answer
487
views
Is This Scheduling Problem NP-Hard?
The scheduling problem (arising from distributed computing) is defined as a decision problem as follows:
Instance:
A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, p_{n-...
- 2,329
4
votes
1
answer
651
views
Hardness of node partitioning under shortest path constraint
Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in R$ (negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less)...
- 283
4
votes
1
answer
206
views
Is Optimal Swap Sorting NP-Hard?
Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to this question, the problem is NP-Complete but the reference given proves NP-Completeness ...
- 135
4
votes
1
answer
242
views
How hard is it to determine the chromatic number of a unit distance graph?
For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?
- 14k
4
votes
1
answer
218
views
Limits of variants of Independent Set?
Independent Set (IS) is the $\mathsf{NP}$-complete decision problem
Input: graph $G$ with $v=|V(G)|$, integer $k$
Question: is there an independent set $S \subseteq V(G)$ with at least $k$ vertices?
...
- 19k
4
votes
1
answer
224
views
Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?
The usage of an $\mathrm{NP}$-oracles which delivers a witness has been proposed for example in [Buss1995]. I would like to see an example of an $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard problem. Can ...
- 173
4
votes
2
answers
203
views
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
- 421
4
votes
1
answer
103
views
Complexity of finding a path visiting all leaves on a tree while respecting a distance bound
I am interested in the complexity of a specific variant of the Hamiltonian path problem where we want to visit all leaves of a tree while respecting a distance bound. Formally, given an (undirected, ...
- 9,269
4
votes
1
answer
185
views
Finding a "typical" path
Consider an undirected graph with two distinguished nodes $u\neq v$. How hard is it to find an $u-v$ path, such that its length is as close to the average $u-v$ path length as possible?
Formally, for ...
- 11.4k
4
votes
2
answers
739
views
Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?
Consider the following problem:
Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a
partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, ...
- 49
4
votes
1
answer
1k
views
Hardness of 3-dimensional matching variant
I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose ...
- 43
4
votes
1
answer
150
views
Neighborly properties in a bipartite graph
Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors.
Question: Decide whether there exists a subset $...
- 183
4
votes
1
answer
115
views
From Lasserre maps to pseudo-distributions
Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is ...
- 1,453
4
votes
1
answer
295
views
Find worst case input for a program solving an NP-hard problem
I am trying to find a way to find a worst-case input for a black-box implementation of an algorithm with worst-case exponential runtime.
The problem that the program solves (integer linear ...
- 151
4
votes
0
answers
284
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 20.9k
4
votes
0
answers
103
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- ...
- 10.5k
4
votes
0
answers
94
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={...
- 61
4
votes
1
answer
83
views
Solving an LP with at most m-1 nonzeros
Consider the linear program:
$$
A x = b, ~~~~~~ x\geq 0
$$
where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$.
It is known that, if this ...
- 2,222
4
votes
0
answers
75
views
Hardness of ancilla free quantum circuit extraction from circuit with ancillas
Is there any known result regarding the hardness of the following problem:
Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that ...
- 141
4
votes
0
answers
192
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$ ...
- 51
4
votes
0
answers
175
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$ ...
- 41
4
votes
0
answers
307
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$...
- 342