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