decision problems that are at least as hard as NP-complete problems

learn more… | top users | synonyms

3
votes
0answers
32 views

Minimum edge deletion partitioning of a planar graph

I'm interested in the time complexity of the following problem: Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
1
vote
1answer
49 views

NP-hardness reductions

Suppose I have two generic problems $A_{1}$ and $A_{2}$: the instance of $A_{i}$ is a graph $G$ and a number $t$, and the question is whether a certain parameter $P_{i}(G)$ is at least $t$. Suppose ...
4
votes
0answers
89 views

Bin packing with twin items

Assume we are given $k$ bins of capacity $b$ and $n$ items with integral sizes $x_1,\dots,x_n$. The bin packing problem is to decide whether there exists an assignment of items to bins such that no ...
3
votes
1answer
68 views

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets: If the set resulting from the union, intersection, or Cartesian product of two ...
4
votes
2answers
111 views

Minimum edge deletion partitioning

I'm interested in the time complexity of the following problem: Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the ...
-1
votes
0answers
45 views

How can I prove that scheduling problem F2//Lmax is NP-Hard?

I'm trying to solve it via reduction to the 2-Partion problem. All online resource are leading to a single solution, which is: http://i.imgur.com/mkPrCzb.png (taken from ...
1
vote
1answer
30 views

Showing NP-hardness by reducing from a search problem

I'm comfortable with showing NP-completeness of a decision problem: just take some problem that is known to be hard and reduce it to your new problem. This establishes NP-hardness of the new problem. ...
2
votes
1answer
48 views

Hardness of problem related to number of subsets that satisfy a particular property

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example: ...
2
votes
1answer
39 views

Find the subset of k element between n that maximize the total distance

Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm. ...
0
votes
0answers
24 views

How can I determine whether a problem is NP-Hard [duplicate]

So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case? Suppose I have different groups of people m in a list M= {m1, m2} ...
6
votes
1answer
59 views

Is weighted XOR-SAT NP-hard?

Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a positive cost $c_1,\ldots,c_n\in\mathbb{Z}_{>0}$ and a boolean function $f$ on these variables given in the form ...
0
votes
0answers
26 views

NP-Hard vs NP-Complete Why NP-complete so important? [duplicate]

A problem $L$ is NP-complete when:- $L\in \text{NP}$ For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$ When at least property 2 is satisfied for a problem $L$ (but ...
4
votes
3answers
143 views

Could an NP-hard problem have a mechanical or physical solution method?

Is there any NP-hard problem that we can find a mechanical "polynomial time" solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we ...
1
vote
0answers
14 views

A query regarding the Max3SAT Approximation Algorithm's Application

Its known that a polynomial time Approximation Algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP. If given that the given 3MaxSAT is satisfiable, it is still difficult to find a 7/8+e ...
6
votes
1answer
39 views

Hardness of a problem related to set cover

Suppose $C_1, \ldots, C_m$ are subsets of $\{1, \ldots, n\}$. The goal is to find the smallest subcollection of $C_1, ..., C_m$ such that each element of $\{1, \ldots, n\}$ appears at least $k$ times ...
1
vote
1answer
64 views

Is the Euclidean TSP weakly NP-hard?

So the Euclidean TSP decision problem is NP-complete (see http://dx.doi.org/10.1016/0304-3975(77)90012-3 ) so the TSP optimization problem should be NP-hard. On the other hand there is a PTAS for the ...
5
votes
0answers
165 views

Time Complexity of a Knapsack-derived problem

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
2
votes
0answers
33 views

Hardness of a maximum contiguous subarray sum for a sparse multi-dimensional array

Suppose we have a d-dimensional array A (d > 1) where each dimension has length n. The array is given in sparse notation as input, and the number of given non-zero elements is N. We want to find a ...
1
vote
1answer
73 views

NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
9
votes
4answers
250 views

Can finding a witness be NP-hard even if we already know there is one?

The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand. Suppose that we have a problem in which ...
1
vote
1answer
62 views

Lower bounding the minimum equivalent graph

The transitive reduction $G^t = (V,E^t)$ of a graph $G=(V,E)$ is the smallest graph with the same reachability as $G$ with the property $E^t \subseteq V \times V$. The minimum equivalent graph $G' = ...
0
votes
1answer
94 views

Is the weighted transitive reduction problem NP-hard?

The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$. When $E^t \subseteq E$ it is NP-complete. ...
3
votes
1answer
50 views

Pseudo polynominal time algorithm for Np-Complete Problems

For problems like knapsack there is pseudopolynominaltime algorithm and it is np-complete. So we reduce every other problem in np in polytime to knapsack. But why don't we have then a ...
5
votes
2answers
337 views

Richard Karp's 21 NP-Hard problems, the meaning of his research?

In Richard Karp's paper "Reducability among combinatorial problems" he lists 21 NP-Hard problems. Though I can somewhat understand the ideas and motivation behind the paper I am searching for some ...
0
votes
1answer
40 views

Not Hamiltonian is in NP Class? [duplicate]

I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest. From this book and other study in complexity theory, I have seen the following ...
2
votes
1answer
85 views

Questions on Graph and Hamiltonian [closed]

From this book and other study in complexity theory, I have seen the following statement: The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ...
7
votes
1answer
140 views

Hardness of a constrained quadratic maximization

Consider the following quadratic maximization: \begin{align} \max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x} \end{align} with \begin{align} \mathcal{X} = \lbrace ...
1
vote
1answer
44 views

How can Weighted MaxSAT be in $FP^{NP}$ when dealing with large weights?

Weighted MaxSAT is in $\mathrm{FP^{NP}}$, see [1] Theorem 17.4, i.e. Weighted MaxSAT can be solved with at most a polynomial number of calls to a SAT oracle. The proof in [1] makes use of binary ...
0
votes
1answer
68 views

Is this problem P or NP?

Given a set of whole numbers $M=\{z_0, ..., z_n\}$ Are there $z_i$ and $z_j$ with $i \neq j$ but $z_i = z_j$? Is this Problem (surely or only probably) in $P$ or in $NP$? Is it $NP-hard$?
2
votes
0answers
51 views

What is the trick of “adding a huge number” for in the reduction from $\textsf{3-Partition}$?

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following ...
2
votes
1answer
56 views

Reduction from a further constrained problem

If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard? Generally, this is probably not the case. For ...
1
vote
1answer
34 views

Hardness of 3SAT-k

According to these scribe notes (and a paper), 3SAT-5 is NP-hard. The problem is defined to be: given a 3SAT formula, each variable occurs in at most 5 clauses. It is also proven that 3SAT-4 is ...
2
votes
1answer
30 views

Does randomness makes exponential difference?

Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the ...
1
vote
0answers
79 views

Is the multiset - subset sum problem variant not in NP?

If the input for a subset sum problem is a multiset (with repetitions) instead of a set (without repetitions), e.g. Set $a = ...
1
vote
1answer
44 views

Kth largest subset for small K

The $K$th Largest Subset problem is often given as an example of an NP-hard problem. However, the assumption is that $K$ is unconstrained, and can be as large as $2^n$. Clearly, if $K \le 3$ the ...
3
votes
1answer
29 views

What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean?

I'm reading about a Turing Machine $M$ and it says the problem of deciding whether M accepts a string is "$\Sigma^0_2$-hard and $\Pi^0_2$-hard". I haven't seen this kind of notation before and ...
1
vote
2answers
110 views

Maximum non-intersecting subset of circles

We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$. All the circles have radius of $k$. ...
1
vote
1answer
95 views

Shortest walk that covers $k$ nodes

I have the following problem, I would like to know an efficient algorithm to solve it. Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex ...
4
votes
1answer
190 views

Reducing Exact Cover to Subset Sum

Show that the subset sum problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint: Use ...
8
votes
3answers
175 views

Is $NP$ “minimal”, i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Suppose $\Pi$ is a decidable decision problem. Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard? Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim ...
3
votes
2answers
72 views

Can someone provide a trivial example to the “reduction” procedure used to prove hardness? [duplicate]

I cannot comprehend how you can prove hardness between two NP complete problems. For example, let X be a NP hard problem, I want to prove Y is also NP hard. I can do this by reducing X to Y, if Y is ...
0
votes
1answer
95 views

Problem A is polynomially reducible to problem B…what can we say about A and B?

This is a question on a practice final. Problem A is polynomially reducible to problem B. Which of the following statements is correct? I. If problem A is solvable in a polynomial time then problem ...
8
votes
0answers
118 views

Is finding a weight-balanced tree NP-hard?

In the following, we are considering binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of its weighted leaves. Let $T.l$ and $T.r$ be the left child and ...
0
votes
1answer
25 views

Extended knapsack: is it NP-complete? [closed]

I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same: Maximize the value of ($\sum_{i=1}^n v_i \cdot x_i) + B \cdot ...
3
votes
1answer
47 views

PARTITION with 0-sum assumption

The PARTITION problem: $\{\{x_1,...,x_n\}: \exists I\subseteq[n], \sum_{i\in I}x_i=\sum_{i\notin I}x_i\}$ is well known to be NP-complete. My question: does the partition problem remain ...
0
votes
3answers
80 views

Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes. I want to show that this problem is NP-hard. Is there any ...
5
votes
0answers
87 views

NP-hardness of a special traveling salesman problem

Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$. Is it NP-hard to solve the traveling ...
1
vote
2answers
89 views

Is the Weighted Maximum Coverage Problem with frequency weights NP-hard?

I want to prove the following case of Weighted Maximum Coverage problem with special weights is NP-hard. But I have no idea. So I am here seeking for help. The Weighted Maximum Coverage problem is ...
1
vote
1answer
133 views

Is the maximum coverage variant of Vertex Cover also NP-hard?

In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible ...
2
votes
1answer
58 views

Is ecological bin packing NP-hard?

The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as: Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, ...