1k views

### Is Weighted Vertex Cover NP-Complete? [duplicate]

I'm doing practice problems for an upcoming exam and I'm unsure if the following problem is NP-complete. If it is can you please give me a hint as to what problem I should reduce to it. I believe it's ...
36 views

### HITTING SET Problem [duplicate]

HITTING SET INSTANCE: collection C of subsets of a set S, positive integer K. QUESTION: Does C contain a hitting set for C of size K or less, that is, a subset S' of S with |S'| <= K and such ...
32 views

### When proving a problem is NP-C, how do I select another NP-C problem for the transformation? [duplicate]

I'm taking an algorithms course in which we are discussing proofs that problems are NP-Complete. Our proofs usually take the form: Given a problem $\Pi$, 1. Prove that $\Pi$ is NP. 2. Select an NP-...
30 views

### Gain the Mastery of prooving NP Complete Problems [duplicate]

I want some piece of advice on how can I improve my capability of proving NP-completeness of problems. I am well known with all the concepts theoretically but when it comes to solving down, I get ...
15k views

### What are common techniques for reducing problems to each other?

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
943 views

### Prove that finding largest subset of undirected graph that is almost independent is NP-hard

A subset $S$ of vertices in an undirected graph $G$ is called almost independent if at most 100 edges in $G$ have both endpoints in $S$. Prove that finding the size of the largest almost-independent ...
901 views

### Negative simple path NP-Complete

Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$ My approach was to ...
170 views

### Has anyone seen a NP graph problem like this before?

I have a following graph-based problem: Input: positive integers K and L, undirected graph G I have to choose K vertices from this graph In the path between each pair of chosen K vertices there ...
183 views

### How to prove NP-hardness from scratch?

I am working on a problem of whose complexity is unknown. By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use. Finally, I have decided ...
457 views

### NP Completeness of 3-SAT problem [closed]

I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the ...
458 views

### Check if K-Sum Variation is NP-Complete

Problem Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$. Question This problem came from evaluating some scheduling algorithms that I am ...
639 views

### Showing party invitation problem is np-complete

Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like ...
387 views

### DFA accepts common strings, reduction to NPcomplete

$B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each$M_i$is a DFA and all of the$M_i$accept some common string.} \}$ I'm trying to show that B is NP-complete. I know I have to reduce it to ...
Let $X$ be some problem known to be in $NP$. What is the natural next step in exploring the complexity of the problem? Is it trying to prove whether it is in $P$ or try to prove it is $NP$-Hard? ...