Given a finite simple directed graph $G = (V, A)$, I am looking for a subgraph $G' = (V', A')$ of $G$ such that, for each vertex $v'$ of $V'$, the in-degree and the out-degree of $v'$ are at most one, and the number of arrows $\lvert A' \rvert$ is maximized. In other words, I am looking for a subgraph of $G$ such that:
- For each $v' \in V'$, there exists at most one arrow $(u \to v') \in A'$ s.t. $u \in V'$,
- For each $v' \in V'$, there exists at most one arrow $(v' \to w) \in A'$ s.t. $w \in V'$,
- Cardinality $\lvert A' \rvert$ of $A'$ is maximum with respect to properties 1 and 2 above.
Does this construction of a subgraph have an accepted name? If so, any references for computing such a subgraph are appreciated.
I couldn't find a good reference for this, but I'll give a sketch of how to find an optimal solution in polynomial time. Given $G = (V,A)$, we construct a bipartite graph $G' = (V', V'', E)$ where $V'$ and $V''$ are copies of $V$ and for each arc $uv \in A$ we have a corresponding edge $u'v'' \in E$. Then a maximal matching in $G'$ corresponds to a maximal subgraph in $G$ obeying the in- and out-degree bounds.
I do know that a solution with $|A'| = |V|$ is sometimes called a disjoint vertex cycle cover. Another related notion is an $(f,g)$-factor: given a directed graph $G = (V,A)$ and functions $f,g : V \rightarrow \mathbb{N}$, an $(f,g)$-factor is a spanning subgraph of $G$ in which each vertex has the in- and out-degrees prescribed by $f$ and $g$, respectively. Relaxing this so that $f$ and $g$ only give upper bounds on the degrees gives a generalization of your problem, but I couldn't find and explicit reference to this.