A$1-3.$ Donors.

A directed graph G $=($V$,$E$)$ consists of a vertex set V and a collection E $($V $\backslash$times V$)$ of ordered pairs that represent directed edges which we will refer to as arcs. Consider the following example directed graph and associated integer linear program:

$8$jJUrTR$5$xXP$3$Vw

max

$36$

$247$

$15$

X $->$

$\{$xij : ij is an arc$\}$

x$12+$ x$15<=1$ x$23<=1$

x$34<=1$

x$41+$ x$45<=1$ x$56<=1$

x$63+$x$64+$x$67<=1$ x$75<=1$

x$41=$ x$12+$ x$15$

x$12=$ x$23$

x$23+$ x$63=$ x$34$

x$34+$x$64=$x$41+$x$45$ x$15+$x$45+$x$75=$x$56$ x$56=$x$63+$x$64+$x$67$ x$67=$ x$75$

$0<=$xij $<=1$

xij integer

$($a$)$ Since all variables are binary, we may associate a subgraph to any feasible solution x of $->$

the above IP$,$ namely the subgraph consisting of all arcs ij such that xij $=1.$ Provide

$($foreveryarc ij$)->$

$($for every arc ij $)$

$->$

$8$jJUrTR$5$xXP$3$Vw

the list of all possible subgraphs of the above graph one can get from a feasible solution

to the above IP $($i$.$e$.,$ for every feasible solution x$,$ list the corresponding subgraph$).->$

Hint: We say ij is chosen in a feasible solution x if xij $=1.$ For each vertex i in the graph, there are two constraints added in the program above. One states that the number of chosen arcs entering i equals the number of chosen arcs leaving i$.$ The other states that at most $1$ arc leaving i is chosen.

$($b$)$ Provide an optimal solution and write the optimal value of the above IP$.$ No justification required.

You are in charge of organ donor assignment in the following scenario. You are given a list of parent and child pairs in which each child requires an organ and each parent is willing to donate an organ only if their child receives an organ transplant. There are strict constraints on which parents can donate to which children based on blood type and other medical

considerations. You are given this data in the form of a directed graph G $=($V$,$E$)$ where $->$

each vertex represents a parent and child pair and ij is an arc in G if and only if the parent in vertex i has an organ compatible with the medical needs of the child in vertex j$.$ We assume in this list of parent$/$child pairs that no parent is compatible with their own child, i$.$e$.,$ there are no self$-$loops in G$.($Otherwise that parent would donate to their own child and we can take them out of consideration in this problem.$)$

$($c$)$ Formulate the problem of maximizing the number of children who receive an organ as an integer linear program. You should be able to achieve this by only using binary variables xe for each arc e in E$.$ Work hard $-$ an incorrect formulation would mean childrens$$ lives are at stake!

$->->($d$)$ A directed cycle in G is a list of distinct vertices v$1,$ v$2,...,$ vk in V such that v$1$v$2,$ v$2$v$3,$

$->$

$...,$ vkv$1$ in E$.$ A collection of directed cycles is said to be vertex$-$disjoint if no two

cycles in the collection intersect in a vertex $($i$.$e$.,$ every vertex in V lies inside at most

one directed cycle in the collection$).$ We say a vertex is covered by such a collection

if it is contained in one of the cycles in the collection. In the directed graph drawn

above for example, $56,67,75$ is a directed cycle; alternatively we will say that $(5,6,7)$ is a directed cycle in the example graph. The collection of cycles $\{(5,6,7),(1,2,3,4)\}$ is vertex$-$disjoint, but $\{(1,2,3,4),(4,5,6)\}$ is not.

Prove that in any directed graph G with no self$-$loops, the maximum number of or$-$ gan recipients possible is equal to the maximum number of vertices in G that can be simultaneously covered by a collection of vertex$-$disjoint directed cycles in G$.$