\documentclass[11pt,english]{article}
\usepackage{a4wide,epic,eepic}
\usepackage{babel}
\newcommand{\dom}{\rightarrow}
\newcommand{\2}{\vspace{2mm}}
\newcommand{\qed}{\hfill$\diamond$}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{problem}{Problem}
\newtheorem{conjecture}{Conjecture}
\newcommand{\3}{\vspace{3mm}}
\begin{document}
\title{Second set of exam problems for the course 'Combinatorial Optimization' (DM867) spring 2022}

\author{J\o{}rgen Bang-Jensen\\
Department of Mathematics and Computer Science\\
University of Southern Denmark}



\date{The problems are available from the course page as of April 4, 2022
 The solutions must be uploaded via Itslearning no later than 
Monday May 2, 2022  at 9 a.m.
}

\maketitle
Note  the following important points:

\small{
\begin{itemize}
\item There are 75 points to earn. 
\item You must work alone.
\item
It is important that you explain how you obtain your answers and argue
why they are correct. 
\item If you are asked to describe an algorithm, then
you must supply enough details so that a reader who does not already know
the
algorithm (but knows basic algorithms such a searching for a path from $p$ to $q$, finding a maximum $(s,t)$-flow or a minimum $(s,t)$-cut, an alternating path with respect to a given matching in a bipartite graph, etc) can understand it (but you do should not give pseudo code).

\item
 You should also give the complexity of the algorithm when relevant. In particular, when you are asked to describe a polynomial algorithm, you should argue why the algorithm you describe is in fact polynomial.

\item If you are asked to show how to find a certain structure or number, then you must describe a polynomial algorithm for this. 

\item You may use all the algorithms described in the course as subroutines when this is appropriate. That is, if you are asked to do something where one of the
algorithms from the course IS the algorithm (and not just one step in a larger one), then you must still explain the algorithm in detail. 


\item Note also that illustrating an algorithm
means that one has to follow the steps of the algorithm meticulously
(DK: slavisk).


\item {\bf Any exchange of
results/ideas between different students
before 9 a.m. May 2, 2022  will be considered as exam fraud.}
\end{itemize}
}
\vspace{2mm}

\newpage

\subsection*{PROBLEM 1 (15 point)}

Consider the instance $<K_6$, $w>$ of TSP shown in Figure \ref{TSPfig}.
\begin{figure}[h!]
\begin{center}
\setlength{\unitlength}{0.00045in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(4667,5490)(0,-10)
\put(2355,4965){\blacken\ellipse{284}{284}}
\put(2355,4965){\ellipse{284}{284}}
\put(555,3660){\blacken\ellipse{284}{284}}
\put(555,3660){\ellipse{284}{284}}
\put(555,1815){\blacken\ellipse{284}{284}}
\put(555,1815){\ellipse{284}{284}}
\put(2355,510){\blacken\ellipse{284}{284}}
\put(2355,510){\ellipse{284}{284}}
\put(4155,1815){\blacken\ellipse{284}{284}}
\put(4155,1815){\ellipse{284}{284}}
\put(4155,3660){\blacken\ellipse{284}{284}}
\put(4155,3660){\ellipse{284}{284}}
\path(4155,3660)(4155,1815)
\path(4155,3660)(4155,1815)
\path(555,1815)(555,3660)
\path(555,1815)(555,3660)
\path(2400,4965)(4200,3660)
\path(2400,4965)(4200,3660)
\path(2355,4965)(4155,1770)
\path(2355,4965)(4155,1770)
\path(4200,3615)(510,1815)
\path(4200,3615)(510,1815)
\path(555,3660)(4200,1815)
\path(555,3660)(4200,1815)
\path(600,3660)(4155,3660)
\path(600,3660)(4155,3660)
\path(555,1860)(4110,1860)
\path(555,1860)(4110,1860)
\path(2400,4965)(555,3660)
\path(2400,4965)(555,3660)
\path(600,3660)(2355,510)
\path(600,3660)(2355,510)
\path(2355,4965)(2355,555)
\path(2355,4965)(2355,555)
\path(555,1815)(2355,555)
\path(555,1815)(2355,555)
\path(2445,465)(4155,1815)
\path(2445,465)(4155,1815)
\path(2400,4965)(555,1815)
\path(2400,4965)(555,1815)
\path(4200,3660)(2355,510)
\path(4200,3660)(2355,510)
\put(4560,3615){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}$a$}}}}
\put(4515,1725){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}$b$}}}}
\put(2265,15){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}$c$}}}}
\put(60,1770){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}$d$}}}}
\put(15,3615){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}$e$}}}}
\put(2355,5325){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}$f$}}}}
\put(3345,4425){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(3030,4020){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(2670,3435){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(2625,1590){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(1230,4335){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}3}}}}
\put(1590,3930){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}3}}}}
\put(1590,1455){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}3}}}}
\put(1230,960){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}4}}}}
\put(3255,870){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}4}}}}
\put(1860,3120){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(375,2760){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(4290,2625){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(2895,2760){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(2445,2220){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}4}}}}
\put(3120,1545){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}3}}}}
\end{picture}
}


\end{center}
\caption{An instance of TSP. The weights are as follows: $ab,ad,be,de$ all have weight 1, $ae,af,bd,bf$ all have weight 2, $ac,ce,df,ef$ all have weight 3 and 
$bc,cd,cf$ have weight 4.}\label{TSPfig}
\end{figure}
\subsubsection*{Question a:}
Argue that the instance satisfies the triangle inequality.

\subsubsection*{Question b:} 
Argue that the tree $T=(V,E)$ with $V=\{a,b,c,d,e,f\}$ and $E=\{ab,ac,ad,af,de\}$ is a minimum spanning tree of the complete graph in Figure \ref{TSPfig}.

\subsubsection*{Question c:}
Demonstrate the MST-based 2-approximation algorithm when you start from the minimum spanning tree $T$ and give  the resulting  hamiltonian cycle and its weight.
\subsubsection*{Question d:}
Demonstrate Christofides' algorithm  when you start from the tree $T$ and give  the resulting  hamiltonian cycle and its weight.
\newpage

\subsection*{PROBLEM 2 (15 point)}
This problem is about the Steiner tree problem. 

\subsubsection*{Question a:}
Give a short description of the 2-approximation algorithm for the Steiner tree problem that we have seen in the course.
\subsubsection*{Question b:}
Illustrate the algorithm on the weighted graph in Figure \ref{Steinerfig}
where the black vertices form the set of Steiner vertices (those that must be in the tree).

\begin{figure}[h!]
\begin{center}
\setlength{\unitlength}{0.00045in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(5177,5445)(0,-10)
\put(2625,3615){\ellipse{180}{180}}
\put(1725,2715){\ellipse{180}{180}}
\put(3525,2715){\ellipse{180}{180}}
\put(3075,1815){\ellipse{180}{180}}
\put(2175,1815){\ellipse{180}{180}}
\put(2625,4965){\blacken\ellipse{180}{180}}
\put(2625,4965){\ellipse{180}{180}}
\put(4875,3615){\blacken\ellipse{180}{180}}
\put(4875,3615){\ellipse{180}{180}}
\put(375,3615){\blacken\ellipse{180}{180}}
\put(375,3615){\ellipse{180}{180}}
\put(825,420){\blacken\ellipse{180}{180}}
\put(825,420){\ellipse{180}{180}}
\put(4425,465){\blacken\ellipse{180}{180}}
\put(4425,465){\ellipse{180}{180}}
\path(2625,4965)(2625,3705)
\path(2625,4965)(2625,3705)
\path(375,3615)(1635,2760)
\path(375,3615)(1635,2760)
\path(3120,1725)(4425,465)
\path(3120,1725)(4425,465)
\path(4875,3570)(4425,420)
\path(4875,3570)(4425,420)
\path(4425,465)(825,465)
\path(4425,465)(825,465)
\path(825,465)(375,3660)
\path(825,465)(375,3660)
\path(375,3660)(2580,5010)
\path(375,3660)(2580,5010)
\path(2625,4965)(4875,3660)
\path(2625,4965)(4875,3660)
\path(825,465)(2130,1770)
\path(825,465)(2130,1770)
\path(2625,3525)(2175,1860)
\path(2625,3525)(2175,1860)
\path(2220,1860)(3480,2715)
\path(2220,1860)(3480,2715)
\path(3480,2715)(1770,2715)
\path(3480,2715)(1770,2715)
\path(1815,2670)(3030,1905)
\path(1815,2670)(3030,1905)
\path(3120,1905)(2625,3525)
\path(3120,1905)(2625,3525)
\path(3615,2760)(4875,3615)
\path(3615,2760)(4875,3615)
\put(1185,4425){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(3885,4380){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}3}}}}
\put(4830,1905){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(2625,105){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(195,1905){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}3}}}}
\put(2535,5325){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}a}}}}
\put(5055,3570){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}b}}}}
\put(4605,330){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}c}}}}
\put(735,15){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}d}}}}
\put(15,3660){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}e}}}}
\put(2805,3570){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}f}}}}
\put(3525,2265){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}g}}}}
\put(2940,1320){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}h}}}}
\put(2130,1410){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}i}}}}
\put(1635,2355){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}j}}}}
\end{picture}
}

\end{center}
\caption{An instance of the Steiner tree problem. The black vertices are the Steiner vertices. All edges whose weight is  not shown have weight 1.}\label{Steinerfig}
\end{figure}

\subsubsection*{Question c:}
Is your solution unique?

\subsubsection*{Question d:}
Is the solution optimal?

\newpage
\subsection*{PROBLEM 3 (15 point)}
This problem is about the 2-path problem in acyclic digraphs, that is, we are looking for a pair of vertex disjoint paths $P_1,P_2$ with prescribed end vertices $s_1,t_1$, respectively $s_2,t_2$.
\subsubsection*{Question a:}
Explain  in your own words (you do not need to prove correctness) how to reduce the 2-path problem for an acyclic digraph $D$ to the problem of finding a directed path from a vertex $s$ to a vertex $t$ in another graph $D'$. You should give the running time of the algorithm that you obtain. Hint: see the proof of Theorem 9.2.14 in BJG.

\begin{figure}[h!]
\begin{center}
\setlength{\unitlength}{0.00034996in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(11106,1574)(0,-10)
\put(1489.085,-14.208){\arc{3028.495}{3.5592}{5.7656}}
\blacken\path(2715.775,820.668)(2805.000,735.000)(2766.587,852.577)(2715.775,820.668)
\put(6199.853,-1239.706){\arc{5501.251}{3.8742}{5.5056}}
\blacken\path(8053.209,752.415)(8160.000,690.000)(8095.144,795.327)(8053.209,752.415)
\put(5508.591,-715.554){\arc{3711.115}{3.9296}{5.4237}}
\blacken\path(6607.743,741.945)(6720.000,690.000)(6645.394,788.661)(6607.743,741.945)
\put(6813.591,-715.554){\arc{3711.115}{3.9296}{5.4237}}
\blacken\path(7912.743,741.945)(8025.000,690.000)(7950.394,788.661)(7912.743,741.945)
\put(8195.833,-394.167){\arc{3338.385}{3.7796}{5.5762}}
\blacken\path(9361.520,757.764)(9465.000,690.000)(9405.583,798.488)(9361.520,757.764)
\put(9598.250,-625.590){\arc{3711.182}{3.8631}{5.4601}}
\blacken\path(10749.752,791.084)(10860.000,735.000)(10789.115,836.367)(10749.752,791.084)
\put(3495.915,-1119.329){\arc{5337.199}{3.8417}{5.5149}}
\blacken\path(5308.485,797.885)(5415.000,735.000)(5350.609,840.612)(5308.485,797.885)
\put(105,600){\blacken\ellipse{180}{180}}
\put(105,600){\ellipse{180}{180}}
\put(1455,600){\blacken\ellipse{180}{180}}
\put(1455,600){\ellipse{180}{180}}
\put(4155,600){\blacken\ellipse{180}{180}}
\put(4155,600){\ellipse{180}{180}}
\put(5505,600){\blacken\ellipse{180}{180}}
\put(5505,600){\ellipse{180}{180}}
\put(6810,600){\blacken\ellipse{180}{180}}
\put(6810,600){\ellipse{180}{180}}
\put(8205,600){\blacken\ellipse{180}{180}}
\put(8205,600){\ellipse{180}{180}}
\put(9555,600){\blacken\ellipse{180}{180}}
\put(9555,600){\ellipse{180}{180}}
\put(10905,600){\blacken\ellipse{180}{180}}
\put(10905,600){\ellipse{180}{180}}
\put(2805,600){\blacken\ellipse{180}{180}}
\put(2805,600){\ellipse{180}{180}}
\path(105,600)(1320,600)
\path(105,600)(1320,600)
\blacken\path(1200.000,570.000)(1320.000,600.000)(1200.000,630.000)(1200.000,570.000)
\path(1455,600)(2715,600)
\path(1455,600)(2715,600)
\blacken\path(2595.000,570.000)(2715.000,600.000)(2595.000,630.000)(2595.000,570.000)
\path(2805,600)(4020,600)
\path(2805,600)(4020,600)
\blacken\path(3900.000,570.000)(4020.000,600.000)(3900.000,630.000)(3900.000,570.000)
\path(4155,600)(5325,600)
\path(4155,600)(5325,600)
\blacken\path(5205.000,570.000)(5325.000,600.000)(5205.000,630.000)(5205.000,570.000)
\path(5505,600)(6675,600)
\path(5505,600)(6675,600)
\blacken\path(6555.000,570.000)(6675.000,600.000)(6555.000,630.000)(6555.000,570.000)
\path(6855,600)(8115,600)
\path(6855,600)(8115,600)
\blacken\path(7995.000,570.000)(8115.000,600.000)(7995.000,630.000)(7995.000,570.000)
\path(8205,600)(9420,600)
\path(8205,600)(9420,600)
\blacken\path(9300.000,570.000)(9420.000,600.000)(9300.000,630.000)(9300.000,570.000)
\path(9555,600)(10725,600)
\path(9555,600)(10725,600)
\blacken\path(10605.000,570.000)(10725.000,600.000)(10605.000,630.000)(10605.000,570.000)
\put(15,105){\makebox(0,0)[lb]{\smash{{$s_1$}}}}
\put(1275,105){\makebox(0,0)[lb]{\smash{{$s_2$}}}}
\put(9510,105){\makebox(0,0)[lb]{\smash{{$t_1$}}}}
\put(10815,105){\makebox(0,0)[lb]{\smash{{$t_2$}}}}
\put(2760,105){\makebox(0,0)[lb]{\smash{{$a$}}}}
\put(4110,105){\makebox(0,0)[lb]{\smash{{$b$}}}}
\put(5460,105){\makebox(0,0)[lb]{\smash{{$c$}}}}
\put(6810,105){\makebox(0,0)[lb]{\smash{{$d$}}}}
\put(8160,105){\makebox(0,0)[lb]{\smash{{$e$}}}}
\end{picture}
}

\end{center}
\caption{An acyclic digraph $D$}\label{DAGfig}
\end{figure}

\subsubsection*{Question b:}
Let $D$ be the acyclic digraph in Figure \ref{DAGfig}. Which path in $D'$ corresponds to the solution $P_1=s_1\dom a\dom b\dom d\dom t_1$ and $P_2=s_2\dom c\dom e\dom t_2$?

\subsubsection*{Question c:}

Which solution in $D$ corresponds to the following path in $D'$? 
$${s_1\choose s_2}\dom {a\choose s_2}\dom{a\choose c}\dom{b\choose c}\dom{e\choose c}\dom {e\choose d}\dom{e\choose t_2}\dom {t_1\choose t_2}$$

\subsubsection*{Question d:}
A {\bf feedback vertex set} of a digraph $D=(V,A)$ is a set of vertices $X\subseteq V$ such that the digraph $D'=D-X$ obtained by deleting all vertices in $X$ is acyclic. So for acyclic digraphs the size of a minimum feedback vertex set is zero.\\

Prove that the 2-path problem can be solved in polynomial time on digraphs that have a feedback vertex set of size one. Hint: use that the $k$-path problem is polynomial for acyclic digraphs when $k$ is a constant.

\subsubsection*{Question e:}
Generalize your solution above to digraphs with a feedback vertex set of size at most $2$.

\iffalse
\subsubsection*{Question f (bonus question)}: 

\noindent{}{\bf This question is not in the mandatory part of the exam but will give 10 bonus points if you solve it correctly}\\

Prove that for every constant $k$, the 2-path problem can be solved in polynomial time when the input graph has a feedback vertex set of size at most $k$. You may concentrate (only deal with) the case where we know a feedback vertex set $X$ with $|X|\leq k$ and  none of the vertices $s_1,s_2,t_1,t_2$ belong to $X$.
Hint: consider how a solution can pass through the vertices in a feedback vertex set $X$ of size at most $k$ and use this to reduce the problem to an $r$-path problem in an acyclic digraph.
\fi
\newpage
\subsection*{PROBLEM 4 (10 point)}
Let $G$ be the weighted graph in Figure \ref{CPPfig}.


\begin{figure}[h!]
\begin{center}
\setlength{\unitlength}{0.00034996in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(4322,5445)(0,-10)
\put(2175,5010){\blacken\ellipse{180}{180}}
\put(2175,5010){\ellipse{180}{180}}
\put(375,3660){\blacken\ellipse{180}{180}}
\put(375,3660){\ellipse{180}{180}}
\put(3975,3660){\blacken\ellipse{180}{180}}
\put(3975,3660){\ellipse{180}{180}}
\put(3975,1860){\blacken\ellipse{180}{180}}
\put(3975,1860){\ellipse{180}{180}}
\put(2175,510){\blacken\ellipse{180}{180}}
\put(2175,510){\ellipse{180}{180}}
\put(375,1860){\blacken\ellipse{180}{180}}
\put(375,1860){\ellipse{180}{180}}
\path(2175,5010)(3975,3660)
\path(2175,5010)(3975,3660)
\path(3975,3660)(3975,1815)
\path(3975,3660)(3975,1815)
\path(3975,1860)(2175,510)
\path(3975,1860)(2175,510)
\path(2175,510)(375,1860)
\path(2175,510)(375,1860)
\path(375,1860)(375,3705)
\path(375,1860)(375,3705)
\path(420,3705)(2175,5010)
\path(420,3705)(2175,5010)
\path(2175,5010)(3975,1860)
\path(2175,5010)(3975,1860)
\path(3975,1860)(375,1860)
\path(3975,1860)(375,1860)
\path(375,1860)(2175,5010)
\path(375,1860)(2175,5010)
\path(3975,3660)(2130,465)
\path(3975,3660)(2130,465)
\path(375,3660)(4020,1815)
\path(375,3660)(4020,1815)
\put(2085,5325){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}a}}}}
\put(4200,3615){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}b}}}}
\put(4200,1770){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}c}}}}
\put(2085,15){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}d}}}}
\put(15,1815){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}e}}}}
\put(15,3660){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}f}}}}
\put(3120,4560){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(2580,3795){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(1635,3840){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(1095,4425){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}3}}}}
\put(150,2805){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(825,1050){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(2040,1590){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(3210,960){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}4}}}}
\put(2805,1410){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(4065,2715){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}4}}}}
\put(2130,2940){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{6.0}{\rmdefault}{\mddefault}{\updefault}4}}}}
\end{picture}
}

\end{center}
\caption{An instance of the Chinese postman problem. The numbers indicate the lengths of the edges.}\label{CPPfig}
\end{figure}
\subsubsection*{Question a:}
Let $G,w$ be the instance of the Chinese postman problem shown in Figure \ref{CPPfig}. Show how to find a minimum length set of edges to double (use twice) in $G$ so that one can make an Euler tour in the extended graph $G'$. Show $G'$ and use that to describe a minimum length postman tour in $G$.
\subsubsection*{Question b:}
Suppose now that the length of all the edges is increased by one, so, e.g. the length of $ab$ is now 2. Will the same postman tour still be optimal? 

\newpage

\subsection*{PROBLEM 5 (20 point)}

Let $B=(X_1,X_2,E)$ denote a bipartite graph with vertex set $X_1\cup X_2$ and edges $E$, where each edge in $E$ has one end in $X_1$ and the other in $X_2$. Define two subset systems ${\cal I}_i$, $i=1,2$ on $E$ by letting ${\cal I}_i$ consist of those subsets $E'$ of $E$ where  no two edges in $E'$ share a vertex in $X_i$ for $i=1,2$.
\subsubsection*{Question a:}
Show that for each $i=1,2$ the set system  $M_i=(E,{\cal I}_i)$ is a matroid whose rank function $r_i$ satisfies that $r_i(E')$ is equal to the  number of vertices in $X_i$ which are incident with an edge from $E'$. 

\subsubsection*{Question b:}
Show how the problem of finding a maximum matching in a
bipartite graph can be formulated as a matroid intersection
problem.

\begin{figure}[h!]
\begin{center}
\setlength{\unitlength}{0.0004in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(5492,7558)(0,-10)
\put(600,7394){\blacken\ellipse{284}{284}}
\put(600,7394){\ellipse{284}{284}}
\put(600,5594){\blacken\ellipse{284}{284}}
\put(600,5594){\ellipse{284}{284}}
\put(600,3794){\blacken\ellipse{284}{284}}
\put(600,3794){\ellipse{284}{284}}
\put(600,1994){\blacken\ellipse{284}{284}}
\put(600,1994){\ellipse{284}{284}}
\put(600,194){\blacken\ellipse{284}{284}}
\put(600,194){\ellipse{284}{284}}
\put(5100,7394){\blacken\ellipse{284}{284}}
\put(5100,7394){\ellipse{284}{284}}
\put(5100,5594){\blacken\ellipse{284}{284}}
\put(5100,5594){\ellipse{284}{284}}
\put(5100,3794){\blacken\ellipse{284}{284}}
\put(5100,3794){\ellipse{284}{284}}
\put(5100,1994){\blacken\ellipse{284}{284}}
\put(5100,1994){\ellipse{284}{284}}
\put(5100,149){\blacken\ellipse{284}{284}}
\put(5100,149){\ellipse{284}{284}}
\thicklines
\dashline{120.000}(600,7394)(5145,7394)
\dashline{120.000}(600,5594)(5145,5594)
\dashline{120.000}(600,3794)(5145,3794)
\path(645,7394)(5190,5594)
\path(645,7394)(5190,5594)
\path(600,7349)(5100,1949)
\path(600,7349)(5100,1949)
\path(555,5594)(5100,7439)
\path(555,5594)(5100,7439)
\path(645,5594)(5100,3794)
\path(645,5594)(5100,3794)
\path(645,3794)(5100,5549)
\path(645,3794)(5100,5549)
\path(645,3794)(5100,104)
\path(645,3794)(5100,104)
\path(645,1949)(5145,3749)
\path(645,1949)(5145,3749)
\path(600,149)(5100,3794)
\path(600,149)(5100,3794)
\put(15,7349){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}a}}}}
\put(15,5504){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}b}}}}
\put(60,3749){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}c}}}}
\put(60,1904){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}d}}}}
\put(60,194){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}e}}}}
\put(5370,7349){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}f}}}}
\put(5370,5549){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}g}}}}
\put(5370,3749){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}h}}}}
\put(5325,1994){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}i}}}}
\put(5370,149){\makebox(0,0)[lb]{\smash{{\SetFigFont{9}{7.2}{\rmdefault}{\mddefault}{\updefault}j}}}}
\end{picture}
}

\caption{A bipartite graph with bipartition $X_1=\{a,b,c,d,e\}$, $X_2=\{f,g,h,i,j\}$. The three  dotted edges indicate the current matching.}\label{bipmatchfig}
\end{center}
\end{figure}


\subsubsection*{Question c :}
Give a detailed explanation of the matroid intersection
algorithm specialized to the problem above and indicate 
how the algorithm works by showing how the algorithm finds a
maximum matching in the graph in Figure \ref{bipmatchfig} when it is started from
the matching shown. Does it matter whether we take a shortest $(S_X,T_X)$-path
 or an arbitrary  $(S_X,T_X)$-path for this specialization of the algorithm? 




\subsubsection*{Question d :}
Give a proof of K\"{o}nig's theorem (the size of a maximum
matching in a bipartite graph equals the size of a minimum
vertex cover) based on Edmonds' min-max formula for the maximum
size of a common independent set of two matroids on the same
ground set (Theorem 13.31 in Korte and Vygen). Hint: use your reduction
above and the property of the rank functions or $M_1,M_2$ that you proved in question a.

\subsubsection*{Question e :}
Give a proof of Hall's Theorem (A bipartite graph $B=(U,V,E)$
has a perfect matching if and only if $|U|=|V|$ and 
for all $X\subset U$ the
number of neighbours of $X$ is at least the size of $X$) again
 based on Theorem 13.31 in Korte and Vygen. Note that you must
do this directly. It is not sufficient to show how Hall's theorem
follows from K\"{o}nig's theorem.

\subsubsection*{Question f :}
What is wrong with the following "algorithm" to find a maximum
matching in a general graph $G=(V,E)$: Let ${\cal F}=\{E'\subset
E: \mbox{ no vertex in } V \mbox{ is incident to more than
one edge in }E'\}$ and find a maximum cardinality set in ${\cal F}$
using the greedy algorithm?

\subsubsection*{Question g :}
Describe briefly in words how to use matroid intersection to decide whether
a given bipartite graph has a spanning (i.e. every vertex is covered)
 collection of vertex-disjoint cycles.

\newpage





\end{document}


