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

learn more… | top users | synonyms

1
vote
1answer
34 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after ...
1
vote
1answer
34 views

Find set of non-overlapping rectangles in a 2D grid

I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned ...
4
votes
1answer
43 views

Can we use reductions to design approximation algorithms for NP-hard problems?

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is ...
3
votes
1answer
33 views

Complexity of solving LP with a non-linear growth in variables/constraints

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method. To solve a problem which has $k$ variables and ...
-1
votes
1answer
96 views

How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?

I am studying for NP problems. To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT ...
0
votes
0answers
36 views

In computer science, is there a term that describes a solution set that is guaranteed to contain the solution to a NP hard problem?

Suppose that a NP hard problem involves finding a set $A$, and that there exists a polynomial time algorithm that is able to find a smallest set $B$ such that $A \subset B$. Occasionally, we might be ...
1
vote
0answers
46 views

Why is it NP-hard to learn a disjunction of k variables as a disjunction of fewer than k log n variables?

I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection by R. I. Arriaga and S. Vempala (2006): Further, it is NP-hard to learn a disjunction of k ...
1
vote
1answer
41 views

NP-complete reduction for a k-dumbbell graph

A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete? Proof it is in NP: ...
0
votes
0answers
35 views

Is NP-hardness closed?

Let $X\leq Y$. If $X$ is $NP$-hard, is $Y$ $NP$-hard? I think yes, as if an $NP$ problem is reducible to $X$ in polynomial time, then surely it is also reducible to $Y$ given that $X\leq Y$. If $Y$ ...
-2
votes
1answer
78 views

Reduction from 3SAT [closed]

You are given a directed acyclic graph G = (V, E) in which each node has one “left” out-arc and one “right” out-arc, with a distinguished source node s and sink node t. You are also given a list of ...
2
votes
2answers
38 views

Hardness of approximation: what decision problem is hard exactly?

Just a question for personal comprehension. Consider the following statement: It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 < \epsilon < 1$. ...
0
votes
1answer
29 views

Finding subset such that one sum is more than target and another sum is less

Consider the following problem: Given positive integers $a_1,\ldots,a_n,b_1,\ldots,b_n,A,B$, does there exist a subset $S$ of $\{1,\ldots,n\}$ such that $\sum_{i\in S}a_i\geq A$ and $\sum_{i \in ...
2
votes
1answer
44 views

Proving “QUESTION” is NP-Complete by reduction from n-variable 3SAT [duplicate]

I'm struggling with a problem in my theory of computation course that asks us to prove "QUESTION" is NP-complete by reduction from n-variable 3SAT. I've done a number of other similar reductions but I ...
2
votes
0answers
60 views

Problem related to the Knapsack problem: Is it NP-hard?

I am trying to know whether the following problem is NP-hard: Input: A positive number $k$ and $N$ pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
0
votes
1answer
46 views

Subset-sum variation, multiple sums

Subset-sum problem is NP-complete. I presume so is the problem of determining, given a positive integer $p$, whether in a set of positive integers $\{x_1,x_2,...,x_n\}$ there is a subset which sums to ...
-2
votes
1answer
33 views

What NP-complete problem to reduce to k-Edge-Colorability to prove its NP-hardness?

What known NP-complete problem would one reduce to $k$-Edge-Colorability to prove that the latter is NP-hard?
1
vote
0answers
25 views

NP-hardness of Capacitated Minimum Spanning Tree and Price Collecting Steiner Tree on dag/tree

I am thinking about the NP-completeness of two graph problems on different graph structures. For example: The Capacitated Minimum Spanning Tree for graph is NP-hard. However, is the problem still ...
7
votes
1answer
257 views

NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)

The Google Hash Code 2015 Test Round (problem statement) asked about the following problem: input: a grid $M$ with some marked squares, a threshold $T \in \mathbb{N}$, a maximal area $A \in ...
6
votes
0answers
98 views

Minimum weighted vertex cover on grid graph

Let $G'_{m,n}=(V,E)$ be the grid graph $G_{m,n}$, to which we add "diagonal" edges. For example, here is $G'_{6,3}$: And for each vertex $v_i \in V$, we have a associated positive value $c_i$ ...
0
votes
0answers
45 views

How to solve a problem that is even hard to approximate?

I have a problem that is NP-hard and even NP-hard to approximate within a factor $n^{1-\varepsilon}$ $\forall \varepsilon > 0$. I'm looking now just for approaches that can help me to design a ...
3
votes
0answers
41 views

Is this sparsity constrained convex projection problem NP-hard?

Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$ and an ...
4
votes
1answer
41 views

Hardness of a special GAP-CLIQUE problem

In the GAP-CLIQUE$(k,\ell)$ problem, we are given a graph $G$ over $n$ vertices and have to decide whether $G$ contains a clique of size $k$ or no clique of size $\ell$. Using a PCP system, it can be ...
4
votes
2answers
76 views

Can NP-Hard be converted to NP?

I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem. Can an NP-Hard problem ...
2
votes
1answer
32 views

Complexity of special instance of Knapsack

Consider the following algorithmic task: Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$ Find: integers $d_1,\dots,d_k$ that maximize $\prod_i ...
7
votes
0answers
143 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 ...
2
votes
1answer
72 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
1answer
132 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 ...
10
votes
1answer
238 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
157 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 ...
2
votes
1answer
58 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
55 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
50 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
26 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
84 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
27 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
163 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
15 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
43 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
95 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
438 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
55 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
114 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
293 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
68 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
108 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
98 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
498 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
43 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 ...
3
votes
1answer
88 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
144 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 ...