For this question, it is recommended to read section $1\mathrm{.}5\mathrm{.}2$ of the course text. We refer to the

below integer programming formulation of shortest path $($formulation $(1\mathrm{.}34)$ in the course

text$)$ in a general undirected graph G $=($V$,$ E$)$ with non$-$negative edge weights ce for each

edge e in E:

min X$\{$cexe : e in E$\}$

X$\{$xe : e in $\backslash$delta $($U$)\}>=1($for all U $$ V$,$ s in U$,$ t $$ in U$)($P$)$

xe $>=0($for all e in E$)$

xe integer $($for all e in E$)$

where for any U $$ V $,\backslash$delta $($U$)$ denotes the set of edges in E with exactly one endpoint in the

set U$.$

Consider the following example undirected graph with non$-$negative edge weights indicated

in the figure.

a

s

d

b

c

t

$1$

$6$

$4$

$6$

$2$

$1$

$5$

$20$

$($a$)$ Indicate explicitly the list of variables and the objective function in the above integer

program $($P$)$ for the special case of the example graph above.

$($b$)$ An s$,$ t$-$cut is any set of edges of the form $\backslash$delta $($U$)$ for some U $$ V such that s in U$,$ t $$ in U$.$

Indicate three distinct s$,$ t$-$cuts in the above graph.

$($c$)$ Write out explicitly the constraints in the above integer program $($P$)$ that correspond

to the s$,$ t$-$cuts you identified in the previous part.

$($d$)$ What is the shortest s$,$ t$-$path in the example graph?

$($e$)$ Suppose we delete the constraint xsd$+$xad$+$xab $>=1.$ Does the resulting integer program

still capture the shortest s$-$t path problem? Explain why or why not. What is the

optimal solution to the modified program?

$($f$)$ If we switch the objective function to maximize and add the constraints xe $<=1$ for each

e in E$,$ does the resulting integer program capture the problem of finding the maximum

weight s$-$t path? Explain why or why not. What is the value of the optimal solution to

this modified integer program in the example graph above?