M. Baratto, Y. Crama

The following "cycle selection problem" is motivated by an application to kidney exchange problems. For a digraph G, a cycle selection is a subset of arcs of G forming a union of directed cycles. When the arcs are weighted, the Maximum Weighted Cycle Selection (MWCS) problem consists in finding a cycle selection of maximum total weight. We prove that MWCS is strongly NP-hard.
Next, we focus on the cycle selection problem associated with a complete digraph. We provide four complete ILP formulations of the problem: a "natural" one, featuring an exponential number of constraints which can be separated in polynomial time, and three extended ones. We investigate the relative strength of these formulations. We next concentrate on the natural formulation and on the description of the associated polytope. We prove that it is full-dimensional, and that all the inequalities used in the ILP formulation are facet defining. Furthermore, we describe three new classes of facet-defining inequalities. We also study the problem when we include an additional constraint on the cardinality of a cycle selection. Most of the results proved for the original case remain valid.

Keywords: Graphs, Integer Programming, Polyhedral Combinatorics,


FA1 Graphs and Networks 1
June 11, 2021  9:15 AM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.