Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
2
votes
0answers
287 views

Which complexity information of Ising model is more important?

In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using ...
2
votes
1answer
337 views

Complexity class of a subset problem similar to subset sum

What could be the complexity class of the following problem: Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' \...
2
votes
0answers
162 views

Graph partition with objective over intra-partition weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
2
votes
0answers
74 views

Different hardness proofs w.r.t different classes

Consider a language $L$ which is hard for some class $C$ (e.g. PSPACE-hard). Trivially, $L$ is also $D$-hard for every class $D\subseteq C$ under the same type of reduction (e.g. NP-hard). Is there a ...
2
votes
0answers
142 views

NP-hardness of a winner determination auction

We would need some suggestions for the proof of NP-hardness of an optimization problem. The problem $$ \max_{x_{a,s}} \sum_s \sum_a x_{a,s} q_a \lambda_s \prod_{s' < s} \prod_{a' \neq a} (1 + ...
2
votes
0answers
195 views

Reduction from OR-SAT to Exact CNF-SAT, keeping the number of variables polynomially bounded?

Let me define both the problems first: $OR$-$SAT$: $m$ Boolean formulae are given in $CNF$, $\phi_1$,$\phi_2$, $\ldots$, $\phi_m$, each on variable set, $x_1, x_2, \ldots, x_n$. ($m$ $<$ $2^n$, ...
2
votes
0answers
70 views

Small area containing large amount of patterns

The problem: I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times ...
2
votes
0answers
255 views

Is this variation of the “sequencing with release times and deadlines” problem NP-complete?

The following problem is known to be NP-complete. It can be found in pages 236 and 70 of Garey & Johnson. In this book this problem is known either as ...
2
votes
0answers
252 views

Help with an np-completeness proof [closed]

I know that graph contractability is NP-complete: given $G=(V_1,E_1)$ and $H=(V_2,E_2)$, can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions? Consider the following ...
2
votes
0answers
393 views

Post Correspondence Problem “binary” variant

Bounded Post Correspondence Problem is defined as follows: given list of pairs of words $ (x_1,y_1), \ldots, (x_n, y_n) $ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that $x_{...
2
votes
0answers
201 views

Is there a list of NPC or harder problems for specific real world problem domains? [closed]

The domains of interest to me are: 1. Robotics 2. Search 3. NLP 4. Image feature extraction 5. Network optimization 6. Network security
1
vote
2answers
212 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 ...
1
vote
2answers
241 views

Two Decision Problems About Graphs — Original Results?

I have a couple of short but pleasing results. I was wondering (a) if they're original (b) if so whom should I tell? I don't have easy access to any standard texts that would help me out here. Nor ...
1
vote
1answer
1k views

Removing all but a few cycles in a graph

Let problem $S$ be defined as Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the ...
1
vote
1answer
310 views

Huffman Tree Depth, Is there any theory?

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without ...
1
vote
2answers
2k views

Bin packing approximation with different bin sizes

Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size? More formally, there are $n$ bins of size $b_i$ for $i=1,\dotsc,n$, and $m$ ...
1
vote
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, ...
1
vote
2answers
218 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 ...
1
vote
2answers
1k views

Is longest common subsequence with bounded occurrences NP-complete?

The general longest common subsequence problem (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has m zeros and n ones, where m and n are constants?...
1
vote
1answer
207 views

Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight subset ...
1
vote
1answer
70 views

The decision procedure of theory of closed real field is in NP-hard?

The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
1
vote
1answer
164 views

What languages can be reduced to a NP-complete problem in polynomial time

NP-complete: Language is NP-complete, when it is in NP and every problem in NP is reducible to it in polynomial time. But what languages are reducible to a NP-complete problem (for example SAT) in ...
1
vote
1answer
98 views

3 dimensional matching shortest solution NP-hard?

We have array of arbitrary number of elements - 3d vectors with positive integers components - for example ...
1
vote
1answer
88 views

Minimum number of columns making each row different

I'm curious whether this problem is NP-hard: suppose you are given an arbitrary $m\times n$ 0-1 matrix (each element is either 0 or 1, for the simplicity of the problem), and any pair of rows (i.e. a ...
1
vote
1answer
207 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. ...
1
vote
1answer
258 views

Another edge partitioning problem on cubic graphs

This question was motivated by a closely related problem An edge partitioning problem on cubic graphs Input: at most cubic graph ( maximum node degree is 3) $G=(V,E)$, a natural number $k$ Question:...
1
vote
1answer
541 views

Clique cover problem

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 $...
1
vote
1answer
204 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 ...
1
vote
1answer
672 views

Positive 1-in-3 SAT FPT or Fixed Parameter Intractable

There are a number of satisfiability problems that are difficult to solve even in the fixed parameter sense. For example, Weighted q-CNF Satisfiability is W[1]-complete when parameterized by the ...
1
vote
1answer
335 views

Is there a FNP problem that's NP-hard but not FNP-hard?

For the reductions, choose a class C such that [it's clear what FC means] and FC is not known to be able to solve the satisfaction search problem, and assume that FC indeed can't solve that search ...
1
vote
1answer
346 views

Hardness of XSAT

The standard NP-hard SAT problem is the problem of Boolean satisfiability of conjunctions of clauses, where clauses are disjunctions of literals. I am interested in the problem of the Boolean ...
1
vote
1answer
1k views

Vehicle routing problem over Manhattan distances

I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot. Is the following ...
1
vote
1answer
268 views

Is the following optimization problem (another variant to a previous problem) NP-hard?

This problem is a following up question on this one. The only difference is the addition of $3^{rd}$ constraint "$\sum_{i} x_{ij} \le M$", where M is a constant number. This constraint essentially ...
1
vote
1answer
17 views

Determining if a word of specific length exists that is not accepted by a NFA

It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard? Given an NFA and a ...
1
vote
1answer
127 views

A dominate vector subset sum problem

Let $k$ be some constants (e.g. one can take $k=2$ for simplexity), for any $u,v\in \mathbb{R}$, we say $u$ dominate $v$ if $\forall 1\le i\le k,~ u[i]\ge v[i]$, write it as $u\succ v$. Consider the ...
1
vote
2answers
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 ...
1
vote
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 ...
1
vote
1answer
221 views

Packing sets to maximize overlap

For a set of sets $A$, let $\cup A := \cup_{S \in A} S$. Consider the following problem: Input: a list of $m$ weights $w = (w_1, \ldots, w_m)$, a list of $n$ distinct subsets $T = (S_1, \ldots, ...
1
vote
1answer
230 views

NP-Hardness for an optimization problem

I want to prove that the following optimization problem is NP-Hard. max $\prod_{i = 1}^{N} \frac{\left[\sum_{j =1}^M x_j \mathcal{R}_{ij}\right]^2}{ \sum_{j=1}^M x_j}$ subject to $x_j \in \{0,1\}\...
1
vote
1answer
260 views

Complexity of an edit distance problem

Given an array $A[1...n]$ of non-negative integers, we want to transform $A$ into $A'$ such that $|A[I] - A[I + 1]| \leq 1$ in the minimum number of operations. One operation consist of picking ...
1
vote
1answer
203 views

Efficient verification of Kemeny-optimal rankings

The problem of finding a Kemeny optimal aggregation is as follows: Given items $1 \ldots n$ and a list of partial rankings $q_i$ (i.e. permutations of subsets) of these items, find a ranking $r$ of $1\...
1
vote
0answers
91 views

how to model community detection into np-hard problem

My problem is that given a fully connected graph G={V, E} and a seed set $S=\{s_1, s_2,\dots,s_n\}$, the target is to find clusters under some constrains that the average edge weight within each ...
1
vote
0answers
32 views

Scheduling with Separation Constraint

There are $N$ types of jobs. For each $i$, we have to schedule $T/D_i$ jobs of type $i$ in $T$ timeslots. We know that $\sum_{i=1}^N 1/(D_i+1) = 1$. For each type $i$, the distance between two ...
1
vote
0answers
81 views

Minimum cut with nonlinear objective function

Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum. Let us generalize it the following way: let $f$ be a ...
1
vote
0answers
57 views

Reasoning about NP hardness of optimization problems with closed form functions as input

(This may not be a research level question per se. I can delete this question if the community thinks this way too) I am trying to understand how to reason about hardness of optimization problems ...
1
vote
0answers
97 views

Directed NP Hard Problem on DAG

There are problems that are NP-Hard on undirected graphs(maximum weight independent set and graph coloring) but are polynomial time solvable on trees. Tree decomposition is a good tool to talk about ...
1
vote
0answers
95 views

Best way to represent NP-Hardness result for decision problem with two decision parameters

What is the best way to represent a NP-Hardness result for a decision problem with two decision parameters? Suppose we have a problem $P$ which asks to minimize two parameters $x$ and $y$ and we show ...
1
vote
0answers
85 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 ...
1
vote
0answers
113 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 ...
1
vote
0answers
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 ...