Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
0
votes
1answer
490 views

Formalized configuration of Subset sum problem Worst-case ? [closed]

Is there a formal proof of the worst-case configuration of the subset sum problem? In other words - is there a set proven to be the hardest to find a subset equals to 0 from? thanks
0
votes
2answers
492 views

Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$?

I have the following Equivalent DNF problem: Input:Two DNF formulas, $F_1$ and $F_2$,with variables $a_1,a_2,...a_n.$ Output: $1$ if $F_1$ and $F_2$ are equivalent, $0$ otherwise. $F_1$ and $F_2$ ...
0
votes
1answer
754 views

graph coloring with 3 colors

I'm searching for an algorithm that can calculate a suboptimal solution for: color a graph with 3 colors some vertices already have a color and can't be changed the edges have values and the ...
0
votes
1answer
142 views

Subset Sum Problem and hard looking instances that are not really hard

I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" ...
0
votes
2answers
210 views

NP-hard problems on the class of caterpillars

My question is whether there exist an NP-hard problem that has only a caterpillar as input. By saying only caterpillar as input, I wanted to emphasize that no function (eg: weights on vertices or ...
0
votes
2answers
145 views

Geometric max cover

Consider $n$ points and a distance function $d$ that satisfies the triangle inequality. We are also given a number $r$. Each point $p$ defines a set $B_p$ (or a ball) that covers all other points ...
0
votes
1answer
266 views

NP-complete problems with optimal approximation in poly-time

I'm looking for examples of hard optimization problems, for which we have an optimal approximation (not that this is not the same as $PTAS$, as we require a completely tight approximation, and not $1+\...
0
votes
1answer
356 views

Hardness of an extended maximum set packing problem

(Edited) The maximum set packing problem when the sets are all of equal size, say $k$, is known to be NP-hard for $k \ge 3$. The requirement in this problem is that the sets in the solution will be ...
0
votes
3answers
511 views

Comparing graphs

I am looking for a kick in the right direction. What i am trying to do is to compute "similarity" between two graphs, where I define "similarity" as the number of shared paths. example: ...
0
votes
1answer
74 views

Constrained Topological Sorting with bounded number of chains

In general, constrained topological sorting is NP-hard. Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair ...
0
votes
1answer
243 views

PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem

Problem 1 I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a polynomial time ...
0
votes
1answer
52 views

About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective

Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?
0
votes
1answer
224 views

Is there any reference on the hardness of approximation for 2-partition problem?

I tried to look for some references but could not find any. I knew it is proved to be NP-complete via a transformation from Knapsack or 3DM problem. But I couldn't find a way to apply PCP theorem to ...
0
votes
0answers
59 views

About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
0
votes
0answers
33 views

On approx-preserving P- and A-reducibilities

Let $X$ and $Y$ be two NPO problems. Let $(f,g)$ be a reduction between $X$ and $Y$, in particular, assume that $(f,g)$ is both P-reduction and A-reduction, i.e., there exist two poly-time ...
0
votes
0answers
154 views

NP-hardness of minimizing sum of complicated objective function

In our research, we faced the following problem optimization problem: Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$. Output: $P$, a partition of the ...
0
votes
0answers
418 views

Hardness of Minimizing Submodular Functions with Cardinality Constraints

I am new to submodular functions and I am reading the introductions to submodular functions and applications ( https://www.ima.umn.edu/optimization/seminar/queyranne.pdf ). In this introduction, it ...
0
votes
0answers
70 views

Finding exact value with a quotients of products of random values

Sorry for the haphazard title: really not sure what this should be called Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime). ...
0
votes
0answers
111 views

Minimum Weight Ordering of nodes on a directed graph

I'm bumping my head against the wall trying to prove this problem is NP-complete (it might not be) Let $G = (V,E)$ be a directed graph with weights $w:E \to \mathbb{R_{\geq 0}}$ on the edges. The ...
0
votes
0answers
739 views

Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)

This one's hard, so all help really appreciated! I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it ...
0
votes
0answers
337 views

Maximize Covering Minimizing the Overlap

I have this problem: Given a collection of sets $S:\{S_{1},...,S_{k}\}$ where each set $S_{j}$ is a subset of $U:\{e_{1},...,e_{n}\}$ universe of elements. I would find-out a subset $C \subseteq S$ ...
0
votes
0answers
224 views

Does coNP-hardness imply NP-hardness [duplicate]

Possible Duplicate: Do many-one reductions and Turing reductions define the same class NPC Hi, Is the following true: If L is coNP-hard, then L is NP-hard. I have found statements of this, ...
0
votes
0answers
164 views

np completeness [duplicate]

Possible Duplicate: Reduction Algorithms Hi, I am thinking of researching in this area and am doing some analysis now. Need your help understanding the NP Completeness. I went through the ...
-1
votes
2answers
753 views

What progress has been made to prove whether or not p=np? [closed]

I know that it is still one of the biggest mysteries of computer science whether non-deterministically polynomial problems can be solved in polynomial time. I am curious to know what makes this ...
-1
votes
1answer
51 views

NP-Complete graph problems where a special vertex is given as input?

I am currently working on a graph theory problem where the instance includes a graph and a special vertex in the graph. I am trying to prove the NP-completeness of the problem as well as explore ...
-1
votes
1answer
127 views

Given oracle for Max-3SAT compute clauses that cannot be satisfied

We know that Max-3SAT is NP-hard to compute exactly (and also hard to approximate to a particular constant multiplicative factor). However, suppose you are given an oracle for Max-3SAT that tells you ...
-1
votes
1answer
70 views

Restricted Universe Exact Cover

Apologies for a simple question - I am a beginning graduate student in TCS. Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and ...
-1
votes
1answer
131 views

A conceptual question regarding hardness proofs by reduction [closed]

If we restrict the input domain of a known NP-hard problem P so that this restricted domain is equal to the input domain of another problem S, then show that we can reduce a solution to P given input ...
-1
votes
1answer
61 views

How to make any graph 2-degenerate?

I have to show a PPT(polynomial time reduction) from 'Colorful graph Motif' to '2-Degenerate Steiner Tree'. As input graph should be 2-degenerate, but here is normal graph G (that is, basically an ...
-1
votes
1answer
303 views

What is the simplest known solver for a np-complete problem?

Lets define the simpler of two terms as the one with shortest description length on the untyped λ-calculus. Trying to find the simplest solver for a np-complete problem, I've got this: ...
-1
votes
1answer
134 views

NP Hardness of Metric Steiner Tree

It is known that the metric steiner tree problem is NP hard (Garry and Johnson [1977]). I wanted to know if there is a simpler way of proving the same. Specifically, I am trying to find a polynomial ...
-3
votes
1answer
116 views

Difference between 'Reductions' in algebraic problems vs “Reductions” in Computational Intractability [closed]

When I read NP-completeness for the first time, I really wondered why is the concept of Reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special ...
-3
votes
1answer
311 views

What is meant by “if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP”?

For example, for the $k$-center problem we want to prove that a 2-approximation algorithm is optimal. A proof is presented on page 39 (Theorem 2.4) in Williamson and Shmoys, The Design of ...
-3
votes
1answer
161 views

Can we map this problem to subset-sum?

Let there be $n$ set of ordered pairs $s_1=\{(c_1,f_1),(c_1,f_2) ...(c_1,f_m)\}$, $s_2=\{(c_2,f_1),(c_2,f_2) ...(c_2,f_m)\}$, $s_3=\{(c_3,f_1),(c_3,f_2) ...(c_3,f_m)\}$, .... $s_n=\{(c_n,f_1)(c_n,f_2) ...
-4
votes
1answer
483 views

Prove that the problem of rectilinear picture compression is np-complete

I need a demonstration that the rectilinear picture compression is NP-hard, I know that this fact was proven using 3SAT by Masek in 1978 but I can't find the paper.
-4
votes
1answer
59 views

Proving NP-complete problem

Suppose the following problem: Given an undirected graph G=(V,E), is it possible to choose a subset V' of vertex set V, such that deleting it removes all triangles (cycles of length 3), where |V'| is ...
-4
votes
1answer
206 views

NP-completeness of one generalized subset sum problem (target sum belongs to interval) [closed]

I need to prove that decision problem: for a given set of positive integers $a_1, ..., a_n$, does it exist a subset that sums up to a value within interval $[\frac{1}{2}\sum a_i; \frac{1}{2}\sum a_i+...
-4
votes
2answers
85 views

Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. (notice how many times the 2 is touched [circled in red ...
-4
votes
1answer
416 views

Proving NP-hardness of scheduling problem (total weighted completion time)

Consider the problem $P \mid \mid \sum w_j C_j$. I want to prove that this problem is (strongly) NP-hard by reducing from $3$-Partition, but I am not really sure how to do this. Just to be precise, ...
-5
votes
1answer
537 views

Is 3SAT problem APX-hard or not?

Could you point me a reference, an answer or it is an open question?
-5
votes
2answers
2k views

Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
-5
votes
1answer
86 views

NP hard? Maximize the average for a subset of numbers

Given a set of real numbers, choose a subset to maximize the average subject to the average not exceeding a given threshold. Is it NP hard? I think so, but I cannot come out with a proof. Thanks a ...
-5
votes
2answers
600 views

open problems on $NP$-complete? [closed]

How can we find the list of open problems on $NP$-comlpete?
-6
votes
0answers
157 views

Researching into Special Case of Sudoku is in the $P$ class, and I think I found something mildly interesting about some NP-hard problems

Summary What I find mildly interesting is that there are permutator algorithms that can recover the remaining solution to a Sudoku after a first row is validly solved. I also found out that 3-color ...