We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

558 questions
Filter by
Sorted by
Tagged with
494 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 ...
209 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 ...
424 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 ...
220 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. ...
110 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 ...
410 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 ...
178 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 ...
149 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 ...
169 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....
2k 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 ...
698 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 ...
173 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 ...
170 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 ...
153 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 ...
61 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 ...
107 views

8k 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 ...
201 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 ...
174 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 ...
868 views

### $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 ...
Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $... 1answer 204 views ### Max weight travel on a graph with deadline Given a deadline$D>0$and a complete graph$K_n$(with loops) in which each edge$e_{ij}$has a weight$w(e_{ij}) \ge 0$and a travel time$l(e_{ij}) > 0$. Starting from one of the nodes, we ... 1answer 201 views ### Max-weight connected & co-connected subgraph problem The max-weight connected subgraph problem (MWCS) may be described as follows: given a simple graph$G=(V,E)$and a weight function$w:V\to\mathbb{R}$, one seeks for a subset$L\subseteq V$for which ... 1answer 257 views ### Is deciding whether all satisfying assignments are NAE assignments coNP-complete? Let the language$L$consist of the$k$-CNF formulas$\phi$with the property that any satisfying assignment$x$of$\phi$is a Not-All-Equal (NAE) assignment, i.e. every clause of$\phi$has at least ... 1answer 203 views ### Does a weighted graph have a path with weight zero? Given a weighted digraph$G=(V,E)$, where each edge is associated with a weight (could be positive, negative, or zero). We define the weight of a path to be the sum of the weights along this path. ... 1answer 200 views ### What is the computational complexity of this SAT Variant Given a 3SAT problem. The question being: 'This Problem has exactly K Solutions'? Now, lets say K=1 (without loss of generality). If the problem has a exactly 1 solution and the answer is True. So, ... 3answers 8k views ### Is optimally solving the n×n×n Rubik's Cube NP-hard? Consider the obvious$n\times n\times n$generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ... 1answer 131 views ### A conceptual question regarding hardness proofs by reduction [closed] If we restrict the input domain of a known NP-hard problem P so that this restricted domain is equal to the input domain of another problem S, then show that we can reduce a solution to P given input ... 1answer 155 views ### Is pooling-aware bin packing NP-Hard? I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to ... 1answer 240 views ### totally-mixed 2SAT with exact cardinality? Given a 2HornSAT problem, it’s possible in linear time to find the minimum solution to the problem, i.e., a solution that minimizes the number of variables set to 1. Now let us consider the following ... 2answers 436 views ### Is this vertex ordering optimization NP-Hard? Could you help me to prove that the following problem is NP-hard? Problem. Given an undirected graph$G=(V,E)$, find an ordering of the nodes such that$\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$... 1answer 146 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? ... 2answers 1k views ### When does “X is NP-complete” imply “#X is #P-complete”? Let$X$denote a (decision) problem in NP and let #$X$denote its counting version. Under what conditions is it known that "X is NP-complete"$\implies$"#X is #P-complete"? Of course the existence ... 1answer 914 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$? 1answer 1k views ### Is the following problem NP hard? Consider a collection of sets$F=\{F_1,F_2,\dotsc,F_n\}$over a base set$U=\{e_1,e_2,\dotsc,e_n\}$where$|F_i|\lln$and$e_i \in F_i$, and let$k$be a positive integer. The goal is to find ... 2answers 421 views ### Is intersection of$k \ge 3$graphic matroids in P? It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids. ... 1answer 705 views ### Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard? It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in ... 1answer 226 views ### Vertex isoperimetric number of a graph - NP-hard? The vertex isoperimetric number of a graph$G=(V,E)$is$i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$. Several academic papers state that the problem of computing ... 0answers 31 views ### Sparse coding and matching pursuit algorithms Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ... 3answers 1k views ### Complexity of a subset sum variant Given integers$a_1, \ldots, a_n, b \in \mathbb{N}$. What is the complexity of the following problem $$\exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b?$$ I ... 1answer 252 views ### Hard extendability problems In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other ... 3answers 3k views ### An NP-complete variant of factoring. Arora and Barak's book presents factoring as the following problem:$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$They add, further ... 1answer 1k views ### An edge partitioning problem on cubic graphs Has the complexity of the following problem been studied? Input: a cubic (or$3$-regular) graph$G=(V,E)$, a natural upper bound$t$Question: is there a partition of$E$into$|E|/3$parts of size$...
What is the complexity of the following problem? Input: $H$ a Hamiltonian path in $K_n$ $R \subseteq [n]^2$ a subset of pairs of vertices a positive integer $k$ Query: is there a matching $M$ such ...