Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
568
questions
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:...
asked Oct 28 '10 at 16:52
Mohammad Al-Turkistany
19.5k4 gold badges51 silver badges134 bronze badges
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 ...
