0
$\begingroup$

it is known that the duals of feedback-set problems are set-packing problems; in the context of digraphs the feedback set are either a minimal set of vertices or edges that hit every oriented cycle; the dual is then a cycle-packing of minimal weight (if I understood right)

Question:

how are the graphs that represent the respective dual problems defined, e.g. how can the graph $H$ that represents the cycle-packing problem dual of the minimum feedback-vertex set problem that is represented by graph $G$ (and vice versa)?

$\endgroup$

1 Answer 1

0
$\begingroup$

I finally managed to find what probably is the original description of the equivalence: "The Cycle Cover Problem" 1979 by J.L Swzarcfiter and L.B. Wilson.

In that report the construction of the graphs is described.

From that report it also becomes clear that the constraints on the cycle cover that is equivalent to the feedback set problem is restricted w.r.t. the number $k$ of cycles and not w.r.t. the number of edges per cycle and thus 3DCC that asks for a directed cycle cover without antiparallel edges isn't dual to the minimal feedback vertex set problem listd in Garey and Johnsons collection of NP-complete problems

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.