Questions tagged [np-hardness]
Questions related to NP-hardness and NP-completeness.
560
questions
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
194 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
254 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
391 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
200 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
211 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
301 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
207 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
206 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
154 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
96 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
87 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
206 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.3k4 gold badges51 silver badges133 bronze badges
1
vote
1answer
528 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
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 ...
1
vote
1answer
669 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
334 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
338 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
119 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
219 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
31 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
91 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
111 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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
0answers
27 views
How does one know what is not in a certain class of pseudo-distributions?
We consider working in the function space $\mathbb{R}^{\{ -1,1\}^n}$ where the expectation inner-product makes the juntas form a $2^n$ dimensional orthonormal basis.
Now say one has found a degree $...
1
vote
0answers
182 views
At what parameters is following $NP$-hard?
Problem Instances at given $\alpha>0$.
$(1)$ Given $a_1,\dots,a_{n^\alpha}\in\Bbb Z$ with $|a_i|\in(2^{n-1},2^n-1)$ is there a subset of that sums to $0$?
$(2)$ Given $a_1,\dots,a_{n}\in\Bbb Z$ ...
1
vote
0answers
53 views
About increasing the objective values of certificates for Max-Clique SDP
Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and ...
1
vote
0answers
169 views
Is “Binary Interval Tree” NP-hard? [closed]
The input is set of (disjoint) intervals $I$. The output should be the following rooted binary tree. Each leaf node corresponds to an interval from $I$. Each interior node contains an interval which ...
1
vote
0answers
142 views
Quantum computer versus Random 3-SAT?
It seems to be commonly believed that quantum computer cannot efficiently solve NP-hard problems. What about the challenging problems in average-case, such as Planted Clique and Random 3-SAT?
