<p>Let <span class="math-container">$G = (V,E)$</span> be a directed graph. Define the optimization problem in which the goal is to find a subset of edges in <span class="math-container">$G$</span> of maximum cardinality, such that (i) the in-degree and out-degree of each vertex on this subset of edges is at most <span class="math-container">$1$</span>, and (ii) the induced subgraph on the selected edges does not create cycles. Observe that if there is a Hamiltonian path in <span class="math-container">$G$</span> it is also the optimum for this problem. Thus, this problem is clearly NP-Hard. Are there known approximation-algorithms/lower bounds on approximation that can be applied to this problem? in particular, what is the best approximation we can get to this problem? Note that a 2-approximation can be obtained by finding a maximum matching.</p>
<p>Thank you for the help!</p>

CC BY-SA 4.0
2024-04-07T13:59:20.200Z
This can be solved exactly via a reduction to maximum matching in bipartite graphs. Given $G=(V,E)$ create a bipartite graph $H = (V_1 \uplus V_2, E_H)$ where $V_1$ and $V_2$ are copies of $V$. For each edge $(u,v) in E$ add edge $(u_1,v_2)$ in $H$. Matchings in $H$ correspond to edge sets in $G$ such that the in-degree and out-degree is at most $1$ so max matching $H$ is what you want.
Chandra Chekuri
CC BY-SA 4.0
2024-04-07T14:21:01.237Z
Note that the requirement of in-degree and out-degree is at most 1 can yield cycles.
Chandra Chekuri
CC BY-SA 4.0
2024-04-07T16:32:06.163Z
Oh I am sorry I forgot to mention that the selected edges must form an acyclic graph. I edited the question accordingly.
John
CC BY-SA 4.0
2024-04-09T16:22:36.563Z
A more standard way of phrasing the problem might be that you want to find a pairwise vertex-disjoint set of paths, of maximum total length.
Neal Young
<approximation-algorithms><approximation-hardness><hamiltonian-paths>
Partial Hamiltonian Path Optimization Problem
John
# Partial Hamiltonian Path Optimization Problem

(Asked by: username_0 on 2024-04-07)

Let $G = (V,E)$ be a directed graph. Define the optimization problem in which the goal is to find a subset of edges in $G$ of maximum cardinality, such that (i) the in-degree and out-degree of each vertex on this subset of edges is at most $1$, and (ii) the induced subgraph on the selected edges does not create cycles. Observe that if there is a Hamiltonian path in $G$ it is also the optimum for this problem. Thus, this problem is clearly NP-Hard. Are there known approximation-algorithms/lower bounds on approximation that can be applied to this problem? in particular, what is the best approximation we can get to this problem? Note that a 2-approximation can be obtained by finding a maximum matching.

Thank you for the help!

**Tags:** approximation-algorithms, approximation-hardness, hamiltonian-paths
> **Comments:**
> **username_1**: This can be solved exactly via a reduction to maximum matching in bipartite graphs. Given $G=(V,E)$ create a bipartite graph $H = (V_1 \uplus V_2, E_H)$ where $V_1$ and $V_2$ are copies of $V$. For each edge $(u,v) in E$ add edge $(u_1,v_2)$ in $H$. Matchings in $H$ correspond to edge sets in $G$ such that the in-degree and out-degree is at most $1$ so max matching $H$ is what you want.  
> **username_1**: Note that the requirement of in-degree and out-degree is at most 1 can yield cycles.  
> **username_0**: Oh I am sorry I forgot to mention that the selected edges must form an acyclic graph. I edited the question accordingly.  
> **username_2**: A more standard way of phrasing the problem might be that you want to find a pairwise vertex-disjoint set of paths, of maximum total length.  

---

## 0 answers

