Minimum Feedback Arc Set of Supergraph

55 Views Asked by At

Suppose we start from a directed graph $\mathcal{G}=(V,E)$, where $V$ is the set of vertices and $E\subset V \times V$ is the set of edges. Let $F \subset E$ be the solution to the minimum feedback arc set problem. This is, the graph $(V,E \setminus F)$ is acyclic and for any $H \subset E$ such that $|H|<|F|$ there are cycles in the graph $(V,E\setminus H)$.

Now suppose we take the supergraph $\mathcal{G}'=(V',E')$ with $V' \supset V$ and $E' \supset E$ satisfying $E' \cap (V \times V) = E$ (obviously $E' \subset V' \times V'$). Is there in general a solution to the minimum feedback arc set problem of $\mathcal{G'}$, call it $F'$, satisfying $F' \supset F$?