<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}



%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~38~~~Introduction to Algorithms
                        \hfill Spring 2014} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&amp;$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM
% HERE:


\newcommand{\set}[1]{\left \{{#1} \right \}}

\begin{document}
\problemset{6}{May 20}{\bf May 27}

Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the optional text (CLRS). The full honor code guidelines can be found in the course syllabus.


Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}
\begin{enumerate}
\item Show that problem of finding the maximum cardinality independent
  set in the intersection of {\em three} matroids is NP-hard. That is,
  specify three matroids over a common universe $E$ (prove that each
  is a matroid), together with a
  polynomial-time procedure for each one that determines whether or
  not a set $A \subseteq E$ is an independent set. Then give a
  reduction from an NP-complete problem to the problem of
  determining whether there exists an independent set of cardinality at least $k$
  in the intersection of the three matroids. Hint: reduce from
  Hamilton path in a directed graph.

\item Kernalization. Given a graph $G = (V,E)$ and a parameter $k$, we
  are interested in whether $G$ contains a vertex cover of size
  $k$. Give a polynomial time procedure that produces, from $G$ and
  $k$, an integer $k' \le k$ and a graph $G' = (V', E')$ with $|E| \le
  {k}^2$ and $|V'| \le 2{k}^2$ such that $G'$ has a vertex cover of
  size $k'$ iff $G$ has a vertex cover of size $k$. This results in a
  $O(k^{2k^2} + \mbox{poly}(n))$ time procedure to solve vertex cover
  with parameter $k$. Hint: consider the following two operations: (1) remove a vertex of
  degree greater than $k$ and all of its incident edges, and (2)
  remove an isolated (degree 0) vertex.

\item We are given a directed graph $G = (V,E)$, representing a communication network, together with a source vertex $s$ and a sink vertex $t$. Let $P$ be the set of $s$-$t$ paths in $G$. We are transmitting information along each path $p \in P$, and each path utilizes a $0 \le x_p \le 1$ fraction of the available bandwidth. We want to maximize the total bandwidth utilized; i.e., $\sum_{p \in P} x_p$, subject to the constraint that, for each edge $e$, the sum of the $x_p$ over paths that use $e$ is at most $1$.
    
\begin{itemize}
\item Formulate this problem as a linear program with potentially exponentially many variables. 
\item Write down the dual of this linear program and describe how to interpret the variables as edge weights subject to a constraint on the minimum length path from $s$ to $t$.
\item Argue that the dual linear program can be solved in polynomial time via the ellipsoid algorithm, by describing how to implement a {\em separation oracle} that, given a purported solution, either verifies that all constraints are satisfied, or returns a violated constraint.
\end{itemize}
\end{enumerate}
\end{document} </pre></body></html>