About complexity of Polynomial time (Karp) reduction

Question

[Resource/information request]

I would like to know if, in literature, there exist two languages $L_1$ and $L_2 \in NP$-complete set such that reducing $L_1$ to $L_2$ amounts to solving an instance of a linear programming problem.

Alternatively, I mean, out of all possible reductions, if there is a way to formulate the reduction process as an LP problem.

---

My understanding and motivation:

I see Karp reduction as a polytime algorithm that computes a mapping of a string (an $L_1$ instant) to another string (an $L_2$ instant). Thus, it must solve a functional problem in the FP complexity class.

I want to see if this proposition holds:

"Any Karp reduction can be viewed as solving an instance of an LP problem."

I have built the intuition based on the known result that the decision version of LP is P-complete. Thus, I am looking for languages $L_1$ and $L_2$ and inspect their details.

Note: A direct internet search (with related keywords) is not helping me much. Thus, any pointer or reference would be much appreciated. Thanks!

• Manish Kumar: @D.W., I agree. By 'amounts to,' I mean out of all possible reductions if there is a way to formulate the reduction process as an LP problem.
• Manish Kumar: @D.W., I want to see if this proposition holds: "Any Karp reduction can be viewed as solving an instance of an LP problem." I have built the intuition based on the known result that the decision version of LP is P-complete.
• Manish Kumar: @D.W., Thanks! I have implemented the changes in the post.

Answer 1

The straightforward example is $\text{HAM-CYCLE}\le_P \text{TSP}$.

The following definitions are from CLRS:

$\text{HAM-CYCLE}=\{\langle G\rangle: \text{$G$ is a hamiltonian graph}\},$

\begin{align}\text{TSP}=\{\langle G, c, k\rangle: &\text{$G=(V, E)$ is a complete graph,}\\ &\text{$c$ is a function $V\times V\rightarrow \mathbb{N} ,ドル}\\ &k\in \mathbb{N}, and\\ &\text{$G$ has a traveling-salesperson tour with cost at most $k$}\}.\end{align}

Our task in TSP is to find a Hamiltonian cycle in $G$ while minimize the total cost $c$ of the cycle.

Let $G=(V,E_G)$ is an input graph of $\text{HAM-CYCLE}$ and $G'=(V,E_{G'})$ is the constructed input graph of $\text{TSP}$. Let $e_{ij}$ be a varible denoting edge $(i,j)\in E_G$,

$$e_{ij}=\begin{cases}\text{1ドル,ドル if $(i,j)\in E_G,ドル} \\ \text{0ドル,ドル otherwise.}\end{cases}$$

We construct the reduction so that the cost is 0ドル$ for all edges in $E_G\cap E_{G'}$, otherwise is 1, and set $k=0$. $G$ is Hamiltonian graph iff we can travel all vertices in $G'$ and back with the total cost is 0ドル$.

The LP constraints are $$\text{$c_{ij}+e_{ij}=1,k=0,$ for all $i,j\in V$}.$$

If you want to explicitly construct $G'=(V,E_{G'})$, you can similarly define $e'_{ij}=1$ for all $i,j\in V$ to denote edges in $E_{G'}$. The LP constraints are $$\text{$c_{ij}+e_{ij}=1, e'_{ij}=1,k=0$ for all $i,j\in V$}.$$No objective function is needed.