# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

606 questions
Filter by
Sorted by
Tagged with
268 views

### Determining what can be achieved by a permutation of elements of a noncommutative group

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
709 views

### Edge and vertex fault tolerance in graphs

Suppose we are given two graphs $G$ and $H$, where $H$ is a subgraph of $G$. What is the maximum number $k$ such that if any $k$ edges are removed from $G$, $H$ still remains a subgraph of $G$? What ...
177 views

### Check the match of the maximum of each subset

Given a number of vectors with $n$ elements, i.e., $S=(a_1, \cdots, a_n)$, $T_j=(b_1^j, \cdots, b_n^j)$ for $j=1,\cdots, m$ where each $a_i$ or $b^i_j$ is a natural number. Question: determine ...
85 views

### PTIME or NP-Hardness of stochastic objective function

I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is ...
91 views

### Showing hardness of maximizing stochastic objective function over graph

Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. The challenge is to ...
87 views

### Is NP-complete the existence of paths of a given length in a directed graph? [closed]

Given a directed graph G= (V,E), a pair of vertices s and t, a natural number K encoded in binary, whether the problem to decide there exists a path (not necessarily simple) from s to t of length K is ...
116 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$ ...
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 ...
93 views

### About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective

Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?
516 views

### Proving NP-hardness of scheduling problem (total weighted completion time)

Consider the problem $P \mid \mid \sum w_j C_j$. I want to prove that this problem is (strongly) NP-hard by reducing from $3$-Partition, but I am not really sure how to do this. Just to be precise, ...
527 views

### Testing whether letters can be scheduled to achieve a word in a regular language

I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each ...
241 views

### If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?

NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case. Is there a ...
474 views

### Binary matrix column subset selection complexity

Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no ...
244 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. ...
120 views

### Generalized path cover problem in DAG

Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that ...
440 views

### What is the complexity of this graph problem?

Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and the size of $A$ is ...
184 views

### Minimising the root-set of a spanning hyperforest of a hypergraph

I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for ...
153 views

### Are there any NP-complete for continuous mathematics? [closed]

Looking at this wiki page, it seems most NP-complete problems are based on discrete structures, such as graphs. What are some problems that involve real or complex analysis instead of discrete ...
177 views

### Is Non-linear Constrained Optimal Exact Cover NP-Hard?

Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard....
4k views

### Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
718 views

### Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters? (By k different ...
181 views

### Matrix Coloring under Vertical and Horizontal Constraints

I'm searching for the correct name of the following NP-complete problem. I would also appreciate answers pointing to problems with similar-looking variations. The input consists of A set of ...
177 views

### Reduction of graph chromatic number to hypergraph 2-colorability

I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this ...
201 views

### Geometric max cover

Consider $n$ points and a distance function $d$ that satisfies the triangle inequality. We are also given a number $r$. Each point $p$ defines a set $B_p$ (or a ball) that covers all other points ...
63 views

### Proving NP-complete problem

Suppose the following problem: Given an undirected graph G=(V,E), is it possible to choose a subset V' of vertex set V, such that deleting it removes all triangles (cycles of length 3), where |V'| is ...
305 views

### Maximum Polyhedron Volume in Given $n$ Points

Suppose we are given $n$ points $v_1,v_2,\cdots, v_n\in \mathbb{R}^k$, I want to find $k+1$ points $v_{i_1}, v_{i_2},\cdots,v_{i_{k+1}}$ such that the volume of the convex body spanned by them ...
213 views

### Hardness of exact binomial tail bounds

Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B>t)$. Naively, computing $F$ requires exponential (in $n$) time. ...
235 views

### What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (...
188 views

### Solving linear program with 1 quadratic constraint complexity

Consider the following linear program, \min y \\ xc_1 \leq c_2 + yz,\\ x = x_1 + \dots + x_n,\\ z \leq x_1 + x_2, \\ z \leq x_2 + x_3, \\ \vdots\\ z \leq x_{n-1} + x_n, \\ x,x_1, \dots, x_n,y,z \...
9k 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 ...
298 views

### Is Asymptotic PTAS $\subseteq$ APX?

The definition of asymptotic polynomial-time approximation scheme (Asymptotic PTAS) is defined as follows: A minimization problem $\Pi$ is Asymptotic PTAS if for all $\epsilon$ there exists an ...
255 views

### String version of even-odd partition problem

Motivated by Hardness proof of EVEN-ODD PARTITION post I came up with a string version. String even-odd partition INPUT: $(x_{1,0},x_{1,1}),\dots,(x_{n,0},x_{n,1})$, i.e., $n$ pairs of strings over ...
2k views

### Are there NP-complete problems with polynomial expected time solutions?

Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)? If not, are there problems for ...
2k views

### Tardos Function Counterexample to Blum's $P\neq NP$ Claim

In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6. Theorem 6: Let $f \in \mathcal{B}_n$ be any ...
### $k$-clique in $k$-partite graph
Is the decision whether a $k$-clique exists in a $k$-partite graph NP-hard? I have found only a very limited number of references on this problem, and they seem to be concerned with heuristics to ...