19
The cycle cover problem (CC) is the problem of finding a spanning set of cycles in a given directed or undirected input graph.
If all the cycles in the cover must consist of at least $k$ edges/arcs, the resulting restriction of the problem is denoted $k$-UCC (in undirected graphs) and $k$-DCC (in directed graphs).
The complexity of the directed version is ...
3
The problem you are calling "two-by-two" topological sorting is the Two Processor Scheduling Problem (unit-length jobs, under precedence constraints given by a partial order on the jobs -- i.e., the DAG). The partial order on the jobs constrains them so that if x<y then job y cannot be started until job x is completed. Shelling the vertices of the DAG ...
2
Depending on how people interpret "research-level", this might need to be moved to cs.stackexchange.com.
The intuition becomes more apparent if you first write down an alternate similar looking but not necessarily linear mathematical program
$$\begin{eqnarray}
\textrm{maximize}\,\,&\tfrac{\sum_{(i,j) \in E} x_{ij}}{\sum_{i \in V} y_i}& \\
\textrm{...
Only top voted, non community-wiki answers of a minimum length are eligible
