\documentclass[12pt]{article}

\usepackage{graphicx}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Professor Amin Saberi (saberi@stanford.edu) }
{\\ \bssten HW\#2 --  Due 02/17/09}
\vspace{5pt}

\begin{enumerate}

\item Given a nonincreasing sequence of positive integers $d_1,d_2,\dots,d_n$, suppose 
we wish to construct a simple graph $G(V,E)$ on $n$ vertices where $d_i$ is the degree 
of $v_i \in V$. 
\begin{enumerate}
\item Prove that there exists a simple graph with sequence $d_1,d_2,\dots,d_n$ if and 
only if there exist one with sequence $d_2-1, d_3-1, \dots, d_{d_1+1} -1, d_{d_1 + 2}, 
d_{d_1 + 3}, \dots, d_n$. Use this to design a greedy polynomial-time algorithm to 
construct $G$ or determine that such a graph cannot exist.
\item Now assume the sequence given above is partitioned as $a = d_1, d_2, \dots, d_k$ 
and $b = d_{k+1}, d_{k+2}, \dots, d_n$ for $ 1 \leq k < n$. Show how to use network 
flow to construct a simple bipartite graph $G(A,B,E)$ (or determine that one does not 
exist) such that the sequences $a$ and $b$ describe the degrees of vertices in $A$ and 
$B$ respectively.
\end{enumerate}

\item Given a network $N$ with integral capacities, suppose we wish to identify, from among 
all minimum cuts, a minimum cut containing the least number of edges. Show how to modify 
the capacities in $N$ in order to find the cut with the least number of edges. 

\item Kleinberg and Tardos Problem 7.27

\item Kleinberg and Tardos Problem 7.31

\item Recall that to show a problem $X$ is NP-complete we must show that it is in NP and
construct a polynomial-time computable function that maps inputs of a known NP-complete 
problem to inputs of $X$ (e.g. $3$-SAT $\leq_p X$) in a way that preserves problem satisfiability. 
The last statement would imply that all problems in NP are polynomial reducible to $X$, 
hence $X$ is NP-complete. 

\begin{enumerate}
\item Integer Programming (IP) decision problem asks whether there exists an integer solution $x$
satisfying linear constraints $Ax \leq b$ and with objective value $c^Tx$ at least $k$. Prove that IP is NP-complete.
\item The Clique decision problem asks whether a clique (a complete subgraph) of size $k$ exists in given graph $G$. 
Prove that Clique is NP-complete.
\item Consider a modified version of Clique in which all vertices have degree at most $3$.
Is this problem NP-complete? Why or why not?
\end{enumerate}
(Hint: Use $3$-SAT for above reductions, or any other NP-Complete problem from class)

\item For the selected project submit an (upto) one page write-up describing what 
the central problem is including some history, branches of mathematics involved, 
why the problem is difficult, and what the applications are. Give links to a 
couple of relevant papers and summarize each in a few sentences. It is okay to 
use material from the Project pages but hopefully you can expand a bit on what 
is there now. Finally list some ideas you and your group have on what you can 
accomplish during the remainder of the quarter. Submit only one write-up per group.




\end{enumerate}


\end{document}