# reductions's questions - English 1answer

762 reductions questions.

### 3 A TSP to HamCycle Reduction

I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle ...

### 21 Converting (math) problems to SAT instances

3 answers, 1.540 views algorithms reductions satisfiability
What I want to do is turn a math problem I have into a boolean satisfiability problem (SAT) and then solve it using a SAT Solver. I wonder if someone knows a manual, guide or anything that will help ...

### 3 Reduce Vertex Cover to another Vertex Cover problem

2 answers, 300 views graphs np-complete reductions
Disclaimer: This is a homework question. I would like to reduce vertex cover problem to the following problem: $$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$ I have divided the ...

### 2 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 ...

### On FPTAS and many one parsimonious reductions

We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction. If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have? If $\Pi_2$ has an ...

### 1 Collection of meta-reductions in theory of $\mathrm{NP}$-completeness

3 answers, 18 views np-complete reductions np-hard np
I want to start a wiki post about meta-result of meta-reductions in the theory of $\mathrm{NP}$-completeness. This can be regarded as a reference request post. Any links are appreciated. At least, ...

### Is this reduction from 3D-MATCHING to PATH SELECTION invalid?

1 answers, 12 views np-complete reductions
I'm a bit confused about some proof that PATH-SELECTION-PROBLEM is NP-complete (Problem 9, chapter 8 in "Algorithm Design" by Tardos and Kleinberg) that I found in some solution manual here: https:...

### 1 What are known 3SAT to 2SAT reductions?

Is there a way to convert a 3SAT formula into a equisatisfiable 2SAT formula? Each method is of interest, even those that grow exponentially. (So if, for example, my 3SAT formula has 16 variables and ...

### 1 polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$

If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$ I proved that when $L_{2} \in \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$ ...

### 2 Careful 5COLOR NP hardness

Given the following definition of Careful 5COLORING: A 5-coloring is careful if the colors assigned to adjacent vertices are not only distinct, but differ by more than 1(mod 5) how would a ...

### A Language Belonges to PSPACE

Let $A,B$ be two languages, for which we know: $A \in PSPACE$ $A\le_LB$ Can we conclude from the above that $B \in PSPACE$ ? I think the answer is no, however I don't know how to ...

### Reduction from an assignment problem to an independent set problem: NP-hard

2 answers, 55 views reductions np-hard assignment-problem
The problem I have is as follows: I have a complete bipartite graph $G=(V \cup C,E)$ as input, where $|V|=1, |C|=n, |E|=n$ The interpretation is that the node of $V$ is a vehicle, the $n$ nodes of C ...

### 2-partition reduction for weighted completion time in scheduling

0 answers, 19 views reductions scheduling
I've read about the reduction from 2-partition for the problem of minimizing weighted completion time with release dates but I'm not very experienced in doing reductions so I want to verify that my ...

### Is my logic correct and is this a new reduction and algorithm from 3 SAT to clique?

Is my logic correct? If so, is this a new reduction and algorithm from 3 SAT to clique? I could only find one SAT to clique reduction; it wasn't this. Definitions: A clause group of a SAT instance ...

### Can we reduce an NP to an NP Problem?

Lets say Problem A,B are in NP. Can we reduce Problem A to B? Meaning A $≤_p$ B? or A $≤_t$ B Is there a difference in "hardness" of a Problem even in NP? Or must Problem B at least be NP-Complete?

### Karp Reduction L1 ≤p L2

0 answers, 16 views computability reductions np
Given: L1 = {$0^k1^k$|k ∈ N} L2= {1} L1 $≤_p$ L2 There must be a function $f:$$Σ^*$ $\rightarrow$ $Σ^*$ w ∈ L1 $\iff$ f(w) ∈ L2 Lets say a word in L1 is mapped to 1 in L2. If it is not in L1 ...

### 1 Turing Reduction vs Karp Reduction

When do you use Turing- and when Karp Reduction? What are the advantages and disadvantages? I've read about Karp Reduction mainly used in the Context of reducing a Language: e.g. L1 $≤_p$ L2