# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

578 questions
Filter by
Sorted by
Tagged with
113 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 ...
767 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 ...
357 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$ ...
225 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, ...
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 ...
800 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 ...
53 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 ...
144 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 ...
78 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 ...
132 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 ...
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 ...
307 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: ...
141 views

### NP Hardness of Metric Steiner Tree

It is known that the metric steiner tree problem is NP hard (Garry and Johnson ). I wanted to know if there is a simpler way of proving the same. Specifically, I am trying to find a polynomial ...
92 views

509 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.
106 views

### Example of decidable NP-hard problem that is not NP-complete [closed]

I am looking for an example of a decision problem which fulfills the following conditions: 1. It is decidable 2. It is NP-hard 3. It is not NP-complete All my search attempts yielded examples that ...
30 views

### Dividing digraph to acyclic subgraphs NP completeness

Let G = (V, E) be a directed graph. Consider the problem of dividing V into two disjoint parts A and B such that there does not exist directed cycles in A or B. Prove that this problem is NP-complete ...
62 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 ...