# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

637 questions
Filter by
Sorted by
Tagged with
28 views

### Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
51 views

### Maximize the absolute value of connected nodes after $k$ modifications

Given a graph $G=\{V,E\}$, each node $i$ has a value $v_i$. Given budget $k$, we have $k$ chance to add 1 or minus 1 for a node's value, for example, $v'_i=v_i+1$ or $v'_i=v_i-1$. In particular, $v'_i$...
72 views

122 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 ...
148 views

### Coloring intersection graph of squares

It is known that the coloring intersection graph of axis-parallel rectangles is NP-Hard. What about squares and more specific case "unit squares"? Thanks.
40 views

### Modifying sets to minimize the distance among each pair of the mean value of sets

Given $n$ points, each point $x_i$ has a value $v_i \in \mathbb{R}^{d}$, and there are $m$ point sets $\{S_1,\dots, S_m\}$ that each point set consists of some points. The size of point sets can be ...
My question concerns the NP-hardness of the following discrete optimization problem: Given a matrix $A \in \{ \pm 1 \}^{m\times n}$, $$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm ... 1answer 54 views ### Is time-slot matchmaking NP-hard? I have the following problem, which I intuitively expect to be NP-hard but cannot see how to write a reduction for: Givens: There is a fixed set of time slots, e.g. {9-10, 10-11, 11-12, 12-1, etc.}. ... 1answer 188 views ### \rho OPT + k approximation for bin packing (Unpublished result of David P. Williamson) I am currently stuck on Exercise 5.12 in this book, which is apparently an unpublished result of David P. Williamson according to the book notes. The problem asks to use randomized rounding and first ... 0answers 139 views ### Triangle detection hardness in regular graphs Consider a tripartite graph over n^{1-\epsilon} vertices each in sets I, J, K. Suppose we impose a constraint that every vertex has degree n^\epsilon/c for some constant \epsilon > 0 and ... 0answers 133 views ### Computational complexity of minimum distance of rate \frac{1}{2} codes We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) ... 1answer 338 views ### How hard is this combinatorial optimisation problem? Suppose we have multiple intervals R_1,R_2,...,R_i of non-negative integers. These intervals may overlap and we use R_h(\mathrm{median}) to denote the median integer in the h-th interval R_h, ... 1answer 133 views ### Finding vertex separator such that the induced subgraph has minimal number of edges My problem is related to edge and vertex cuts with a little twist. Given a graph G and two vertexes u and v. I want to find a set of vertexes S \subset V that disconnects u and v such that ... 1answer 71 views ### Covering a binary relation as a union of rectangles Given finite sets X and Y and a subset R\subset X\times Y, I want to express R as a union R=\bigcup_{i=1}^n X_i\times Y_i with n as small as possible. Here, each X_i\subset X and Y_i\... 2answers 358 views ### Proving not NP-complete by non-existence of gadget Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if ... 1answer 214 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 ... 0answers 86 views ### Is there a "common" name for this type of combinatorial optimization problem? I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next ... 0answers 80 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={... 2answers 188 views ### Two valued variant of subset sum problem I'm interested in the complexity of the following problem: Given a multiset S containing only two positive integers a and b, find a k-partition of S that maximizes the sum of part with ... 2answers 369 views ### Is that edge orientation optimization problem NP-hard? Is the following optimization problem NP-hard? Problem. For a given undirected graph G=(V,E), find an orientation of the edges that minimizes the objective value \sum_\limits{u\in V} ~\left( d_{... 1answer 245 views ### Is this edge orientation optimization problem NP-hard? Is the following optimization problem NP-hard? Problem. For a given undirected graph G=(V,E), find an orientation of the edges that minimizes the objective value \sum_\limits{v\in V} ~d_{out}(v)\... 0answers 168 views ### Is this node permutation optimization NP-Hard? Let G=(V,E) be an undirected graph and let \pi be a permutation of the vertices in V. For a node v\in V, we denote by \text{succ}_{\pi}(v) the set of neighbors of v that occur after v in ... 0answers 172 views ### Is the Fermat-Weber problem \mathsf{NP}-hard? Given a set of n points in a Euclidean space, the Fermat-Weber problem asks to find a center that minimizes the sum of distances of points to that center. There are iterative algorithms known for ... 0answers 49 views ### Does a decision oracle imply an algorithm for \mathbb{NP} - hard problems with several parameters? If we consider the decision version of the classical graph coloring problem, then we have some graph G and some integer k and we want to color G with at most k colors. It is well known that, ... 0answers 169 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... 1answer 78 views ### Set cover with small subsets [closed] Has the variant of the Set Cover problem where each set is of size at most d, for some given d, been studied? Is it polynomial-time solvable for d=2 and NP-hard for d=3 like SAT? 1answer 103 views ### Partition vertices of graph into two sets such that there are at least k edges between sets [closed] I have to show that for every integer k, the problem whether the vertices of input graph can be partitioned into two sets such that there are a least k edges between the sets can be solved in ... 0answers 340 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 ... 2answers 108 views ### Knowing if there are two solutions to the subset sum problem I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are ... 0answers 331 views ### NP-hardness for one-dimensional facility location problem with entrance fee for each customer [closed] We have n customers, (x_1, \dots, x_n), sorted on the read line. For convenience, we also use x_i to denote its coordinate on the line. We need to locate m facilities on the real line. We note ... 0answers 80 views ### Is the traveling salesman problem still NP-hard if all edges need to be covered as well? If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard? Given a graph G with non-negative edge weights, is there a circular walk in G ... 1answer 59 views ### How hard is deciding the existence of a polygonization with prescribed perimeter? Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or ... 1answer 219 views ### Why does Dinur's proof of the PCP theorem fail to work for unique games? What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap ... 1answer 316 views ### Is solving the following system of boolean equations NP-hard? I reduced a problem I'm currently working on to the following system of boolean equations:$$ X_i \iff \begin{cases} \bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\ true \\ false \end{cases}  Where $|... 0answers 158 views ### What does it mean by the statement: "a problem is hard to approximate "? In most of the research papers that I have read so far, I often come across the statement of the following form: "the problem is hard to approximate within any factor smaller than some constant&... 0answers 104 views ### reordering a DAG with the minimum changes Consider a DAG$(V,A)$with an initial permutation$(v_1,v_2,…,v_n)$. We want to arrange the$n$vertice in topological order while keeping as many vertices as possible. The problem is: Is it NP-hard ... 1answer 239 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 ... 0answers 77 views ### Is finding the optimal ordering of predicates NP? Assume we want to find the elements from a set of elements$\mathscr{E}$for which all predicates from a set of$n$predicates$\mathscr{P}$evaluate to true. In programming terms, we want to compute <... 1answer 239 views ### Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious? In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between ... 1answer 107 views ### Complexity of acyclicity of a "nondeterministic" graph By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination:$E \subseteq 2^V \times V$. The problem is whether it is possible ... 1answer 323 views ### Is the knapsack variant with small profit and unlimited repetition of items NP-hard? Consider the unbounded Knapsack problem where we are given$n$items of integral weights$w_i$, integral profits$p_i$, and a max weight$W$. The goal is to maximize the total profit$\sum_i x_ip_i$... 2answers 389 views ### find the most similar topological ordering of a dag Given a permutation$L$of the$n$vertices of the directed acyclic graph$G=(V,E)$. Question: is it NP-hard to find the topological order of the$G$that is the most similar to the given permutation$...
Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so ...