\documentclass[letterpaper,leqno,fleqn]{article}

%proofs
%\usepackage{amsthm}

\usepackage[parfill]{parskip}

% graphs
\usepackage{tkz-graph}

%spacing
\usepackage{setspace}

% \commandname[option1,option2,...]{argument1}{argument2}...
% # $ % ^ & _ { } ~ \
% \# \$ \% \textasciicircum{} \& \_ \{ \} \~{} \textbackslash{}

%\usepackage[cm]{fullpage}
\usepackage[top=3cm, bottom=3cm, left=3cm, right=3cm]{geometry}

%use graphics
\usepackage{graphicx}

%mathstuff
\usepackage{amsmath}

\usepackage{centernot}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\newtheorem{examp}[thm]{Example}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{rmk}[thm]{Remark}

\usepackage[retainorgcmds]{IEEEtrantools}

%mathstuff
\usepackage{amssymb}

%\usepackage{wrapfig}

%Floats, figures, etc
\usepackage{float}

%Lists \begin{enumerate}
\usepackage{enumerate}

%Multiple columns \begin{multicols}{N}
\usepackage{multicol}

%Side captions
%\usepackage{sidecap}

%use subfloats
%\usepackage{subfig}

%fancy headers
\usepackage{fancyhdr}

%Pretty captions
%\usepackage[labelfont=bf,font=it,labelsep=endash,format=hang,font=small]{caption}

%scientific notation
\providecommand{\e}[1]{\ensuremath{\cdot 10^{#1}}}

% nice units/fracs
\usepackage[]{units}

% commas in numbers
\usepackage[group-separator={,}]{siunitx}

% for algorithms
\usepackage[ ]{algorithm,caption}
\usepackage{algpseudocode}

% for listings/verbatim
\usepackage{listings}

% for urls
\usepackage{hyperref}
%\def\Tiny{ \font\Tinyfont = cmr10 at 8pt \relax  \Tinyfont}
\def\Hugee{ \font\Hugeefont = cmr10 at 50pt \relax  \Hugeefont}

\begin{document}

% title page
%\author{Jorge Fernando Gomez\\TA: Oludotun Akinlawon}
%\title{STAT 252 LAB Q2\\Assignment \#1}
%\date{2011.01.31}
%\maketitle
%\thispagestyle{empty}
%\let\thefootnote\relax\footnote{I did not collaborate with anyone.}

% no cover page, header
\newpage
\setlength{\headheight}{20.2pt}
\pagestyle{fancy}
\lhead{2012.11.15\\Assignment \#4\\CMPUT 304 LEC A1}
\rhead{1259371\\Jorge Fernando Gomez}
%\captionsetup{font+=it}
\linespread{1.0}

% extra for columns
%\setlength{\columnseprule}{0.4pt}
%\ptsize{10}
%\begin{spacing}{1}
\section{Boolean equation}
\begin{align*}
1. [(C\vee(G\implies F))\implies (E\wedge(G\implies F)\wedge(H\implies C))]\vee\\
2. [(E\vee F\vee\neg G)]\implies (B\wedge C\wedge\neg D\wedge G)]\vee\\
3. [(B\vee\neg C\vee D\vee\neg G]\implies (\neg A \wedge (G\implies F) \wedge(H\implies C))].
\\
\\
\\
	1.[(C\vee(G\implies F))\implies (E\wedge(G\implies F)\wedge(H\implies C))]\\\equiv
	[(C\vee(\neg G\veeF)) \implies (E \wedge(\neg G \vee F)) \wedge (\neg H\vee C))]\\\equiv
	[\neg(C \vee(\neg G\vee F))] \vee (E \wedge (\neg G\vee F)) \wedge (\neg H\vee C))\\\equiv
	(\neg C\wedge \neg(\neg G\vee F))\vee (E\wedge (\neg G\vee F)\wedge (\neg H\vee C))\\\equiv
	(\neg C \wedge G \wedge\neg F)\vee (E\wedge\neg G\wedge\neg H)\vee (E\wedge\neg G \wedge C)\vee (E\wedge F\wedge\neg H)\vee (E\wedge F\wedge C).
\end{align*}

\section{$s$-$t$ Longest-Path Problem} % (fold)
\label{sec:$s$-$t$ Longest-Path Problem}
\begin{enumerate}[a]
\renewcommand\labelenumi{\bfseries\theenumi.}
    \item
    We define the decision problem of finding the longest path, in terms of number edges,
    from $ s $ to $ t $ in
    a directed graph  $ G $ as
    $$ st\mathrm{LPD} = \big\{G=(V,E) :
        \text{Exists a path $ p = s \leadsto t $ of length at least $ k $}. \big\} $$

    \item
    We obtain the length $ m $ of our longest
    path $ p^* $ by
    using our decision problem $ st\mathrm{LPD} $ as an oracle running in $ O(1) $.
    We know that $ |p^*|\le |V| - 1 $.  We can do a binary search over this length,
    using our oracle as a comparison function. The running time of
    binary search is $ O(\log_2 |V|) $.

    \item
    We know $ m $ from part b.  We can reduce the $ st\mathrm{LP} $ functional
    problem to our decision problem by removing some edge $ e $ at a time from our original
    $ st\mathrm{LP} $ instance, and using this as an input for $ st\mathrm{LPD} $, along
    with $ m $.  If a longest path no longer exists when removing $ e $, then we include
    $ e $.  If a longest path still existed with $ e $ removed, then this edge was not necessary
    and we can drop if from our solution.

    We now construct an actual path $ p^* $, initially being only the 1-tuple $ (s) $.
    Let $ S $ denote a current source. Initially $ S \gets s  $.
    We consider every edge $(S, u)$ incident to $ S $.  When we find our necessary $ u $,
    we append $ u $ to $ p $, and then set $ S \gets u $.  The algorithm stops when $ S = t $,
    and our path $ p^* = (s = v_0, v_1,\,\dots\,,v_m = t) $.

    To obtain the running time, we note that for each  $v \in p^* $, we can have potentially
    $ |V| - 1 $ incident edges.  We remove each of these edges individually and consult our
    decision problem in constant time.  We do this at most  $|V| - 1  $ times, and so we have
    a running time of $ O(|V|^2) $.
\end{enumerate}
% section $s$-$t$ Longest-Path Problem (end)

\section{2-CNF-SAT} % (fold)
\label{sec:2-CNF-SAT}
From propositional logic,
we know that $(a \lor b) \Leftrightarrow (\lnot a \Rightarrow b)$.  This means that for
each disjunction $ (a \lor b) $ we can obtain two pairs of implications $ (\lnot a \Rightarrow b) $ and
$ (\lnot b \Rightarrow a) $.  We take each clause in our 2-CNF-SAT instance and transform
them into pairs of implications.

We construct a directed
graph $ G = (V, E) $, where each variable $ x $ in the
set of variables of our transformed 2-CNF-SAT instance corresponds to a vertex $ v \in V $, and where each implication
$ p \Rightarrow q $ corresponds to an edge  $ e \in E  $, where $ p, q $ correspond to some terms
in our transformed instance.  We can now determine in time linear in $ |V| $ and $ |E| $
if our 2-CNF-SAT instance is satisfiable, by determining if we can reach a contradiction of the form
$ (x \Leftrightarrow \lnot x )$.

\begin{prop}
    Let $ A $ be an instance of 2-CNF-SAT with set of clauses $ C $.  For each clause $ c \in C $
    of the form $ (a \lor b )$,
    let $ p(c) = (b \lor a) $, and $ q(c) =  (\lnot a \Rightarrow b)$.
    Let $ S $ be a set of 2-tuples $(a, b)$, where $(a, b)$ implies there exists an implication
    $ (a \Rightarrow b) $ which can be obtained by applying $ q(c) $ or $ (q \circ p)(c)  $ for
    some $ c \in C $, and let $ T $ be a set defined as
    $ T = \{a, b \in T \::\: (a, b) \in S\} $.

    Let $ G = (V,E) $ be
    a directed graph, where
    $ V = T $,  and $ E = S $. Then we can determine the satisfiability of A in polynomial time
    by determining if there exist paths
    $ p_1 : v \leadsto \lnot v $ and $ p_2 : \lnot v \leadsto v  $,
    \mbox{for any $ v \in V $.}
\end{prop}
\paragraph{Proof} % (fold)
\label{par:Proof}
    First, we assume that it is enough to find paths $ p_1 $ and $ p_2 $
    to determine the satisfiability
    of our instance 2-CNF-SAT instance.

    We can determine if $ v $ reaches $ \lnot v $ and vice versa in linear time by constructing
    a BFS tree of $ G $ rooted at $ v $ and rooted at $ \lnot v $. The running time of BFS
    is $ O(|V| + |E|) $, where the cardinalities of both $ V $ and $ E $ are both polynomial
    in the number of variables in $ A $.

    % We now show that it is enough to find $ p_1 $ and $ p_2 $ to determine the satisfiability of $ A $.

    From boolean algebra, we know that for any terms $ p,q $, $ p \land 0 = 0 $, $ p \land \lnot p = 0 $,
    $ p \lor p = p $, and $ (p \land q) = (q \land p) $. Therefore,
    we have that the only way to force a conjunction to be unsatisfiable, is to arrive at
    $ (p \land  0 ) $ or $(p \land \lnot p) $.
    It follows that in order for our instance $ A $ to be unsatisfiable, we must be able
    to reduce our 2-CNF-SAT to an expression containing $ (t \land \lnot t) $ for some variable $ t $ in
    the problem. But we have that $ t = (t\lor t) $, and $ \lnot t = (\lnot t \lor \lnot t) $, and so
    $ (t \land \lnot t) \Leftrightarrow ((t\lor t) \land (\lnot t \lor \lnot t))$.
    \mbox{Furthermore,
    $ ((t\lor t) \land (\lnot t \lor \lnot t)) \Leftrightarrow
    ((\lnot t \Rightarrow t) \land (t \Rightarrow \lnot t))$.}
    We know that every disjunction in $ A $ can be mapped to an equivalent implication,
    and we know implication is transitive.  Therefore, if any such expression can be obtained
    in our original instance, then we can always obtain the equivalent implications.

    We can now show that finding the existence of $ p_1 $ and $ p_2 $ in our
    implication graph is enough to determine satisfiability.

    We have that an edge between any two pair of vertices $ u,v $ exists if and only if
    an implication $ (u \Rightarrow v) $ existed in our transformed 2-CNF-SAT instance for
    corresponding terms of $ u $ and $ v $. Therefore, for any two endpoints $ s, t $ of any path
    in $ G $, we have that $ (s \Rightarrow t) $, and so if we can find paths $ p_1 $ and $ p_2 $,
    we have will have shown
    $(\lnot t \Rightarrow t) $ and $ (t \Rightarrow \lnot t)$.  $ \blacksquare $

% paragraph Proof (end)

% section 2-CNF-SAT (end)

\section{Hamiltonian Path} % (fold)
\label{sec:Hamiltonian Path}
\begin{prop}
    The hamiltonian-path problem is NP-complete.
\end{prop}
\paragraph{Proof} % (fold)
\label{par:Proof}
    We first show that the hamiltonian-path problem belongs to NP. Let a certificate for the problem
    be a path $ p = (v_0,\,\dots\, , v_k)$ where $ k = |V| - 1 $.
    Then we can verify in polynomial time if for every
    \mbox{$ v_{i-1}, v_i \in p $} with $ i \in [1, k] $, there exists edge $ \{v_{i-1}, v_i\} \in E$.

    To prove that it is NP-complete, we reduce the problem from the hamiltonian-cycle problem which
    is NP-complete.  Given some instance $ G = (V,E) $ for the hamiltonian-cycle problem, we define
    a graph $ G^{\prime}  = (V^{\prime}, E^{\prime})$ for the hamiltonian-path problem.
    The vertex set $ V^{\prime} $ has an extra vertex $ u $. Vertex $ u $ corresponds to some
    vertex $ v \in V $, in the sense that $ \{u, w\} \in E^{\prime} $ if and only if $ \{v, w\} \in E $
    for all $ w \in V $.  In addition, $ V^{\prime} $ also contains two other vertices $ x $ and $ y $.
    These two vertices only have one incident edge each: one connects to $ u $, and the other connects
    to $ v $.

    We must show that hamiltonian cycle exists in $ G $ if and only if a hamiltonian path exists in
    $ G^{\prime} $.

    \begin{enumerate}[a.]
        \item
        \textbf{Hamiltonian-cycle $ \Rightarrow  $ hamiltonian-path}:
        We know any hamiltonian-path in $ G^{\prime} $ has to have $ x $ and $ y $ as endpoints
        necessarily, since they have degree 1 each.
        Suppose we can find the cycle $ c = v\leadsto w \rightarrow v $ in $ G $, then we have
        that edge $ \{w, u\}\in E^{\prime} $ since $ \{w, v\} \in E $
        In addition, we know $ v $ and $ u $ are each connected
        to different endpoints $ x, y $. Therefore, we have that the existence of the cycle
        in $ G $ implies a hamiltonian-path
        $ p_h = (x \rightarrow v \leadsto w \rightarrow u \rightarrow y) $.

        \item
        \textbf{Hamiltonian-path $ \Rightarrow $ hamiltonian-cycle}:
        Suppose we have
        $p_h = (x \rightarrow v \leadsto w \rightarrow u \rightarrow y) $.
        We know $ u $ corresponds to $ v $, so we know $ \{w, u\} \in E^{\prime} \Rightarrow
        \{w, v\}\in E $.  Therefore we can remove each endpoint in $ p_h $, and substitute
        $ u $ with $ v $, obtaining the cycle $ c = v\leadsto w \rightarrow v $.
    \end{enumerate}

    We show that it is enough to pick only one $ v \in V $ to correspond with $ u \in V^{\prime} $.
    We know that any hamiltonian cycle has to have all of the vertices in the vertex set. We also
    know that given any hamiltonian cycle, we can obtain a hamiltonian path by removing any edge
    in the cycle.  Therefore we can start our cycle at any arbitrary $ v $, and still obtain
    a hamiltonian path by removing one of its incident edges.  Since we have that $ u $ corresponds
    to $ v $, then we have that we can choose $ v $ arbitrarily and connect our end points
    as described previously.

    We need to show that we can do this reduction in polynomial time. We copy the vertex set
    $ V $ and edge set $ E $ to create $ G^{\prime} $, with the addition of adding three
    new vertices, and at most $ 2 + |V|-1 $ edges.  Therefore our reduction is polynomial.
    $ \blacksquare $
% paragraph Proof (end)

% section Hamiltonian Path (end)

\section{Matrix Max Strips} % (fold)
\label{sec:Matrix Max Strips}
\begin{enumerate}[a]
\renewcommand\labelenumi{\bfseries\theenumi.}
    \item
    Define decision problem as
    $$ \mathrm{MAXSTRIP} = \{M_{m\times n} \::\:
    \text{Exists a permutation of rows of $ M $ where we can obtain at least $ k $ strips.}\}$$

    \item
    \begin{prop}
        MAXSTRIP is NP-complete.
    \end{prop}
    \paragraph{Proof} % (fold)
    \label{par:Proof}
        A certificate will be a specific instance matrix $ A $, and we can check if it contains
        at least $ k $ strips.  We can count the strips easily in polynomial time.

        To prove it is NP-complete, we need to reduce from the hamiltonian path problem.
        Could not solve this one \texttt{:(}
    % paragraph Proof (end)

\end{enumerate}
% section Matrix Max Strips (end)

\section{Independent Set} % (fold)
\label{sec:Independent Set}
\begin{enumerate}[a.]
\renewcommand\labelenumi{\bfseries\theenumi.}
    \item We define the related decision problem to the independent-set problem
    as
    $$ \mathrm{INDSET} = \{G=(V, E) \::\: \text{Exists an independent set of $ G $ of cardinality
    at least $ k $.}\}$$

    \begin{prop}
        INDSET is NP-complete.
    \end{prop}
    \paragraph{Proof} % (fold)
    \label{par:Proof}
    We first show this problem is in NP.  We let an arbitrary subset of size $ k $ be a
    certificate for this problem.  We can verify if it is independent in $ O(|V|^2) $ time
    by checking that none of the vertices in the given set are adjacent to any other.

    To show that it is NP-complete, we reduce from the clique problem, which is NP-complete.
    We let $ G $ be an instance of the clique problem, and we let $ G^{\prime} = G^T$.

    Now we show that $ C \subseteq V $ is a clique in $ G $ if and only if $ C $ is an independent
    set in $ G^T $.
    \begin{enumerate}[a.]
        \item
        \textbf{Clique $ \Rightarrow $ independent set}
        We have that a clique is a complete subgraph of $ G $.  Therefore,
        when we transpose $ G $, none of the vertices in a clique will be adjacent
        to any other vertex in the clique.  That is, the vertices in the clique
        will be independent in $ G^T $.
        \item
        \textbf{Independent set $ \Rightarrow $ clique}
        We have that none of the vertices in an independent set are adjacent to any other
        vertex in the set.  Therefore, when we transpose $ (G^T)^T = G $, we connect
        every vertex in the independent set of $ G^T $ to every other vertex in the set.
        Therefore, we obtain a complete subgraph of $ G $, or a clique in $ G $.
    \end{enumerate}

    We can do the reduction in time $ O(|V|^2) $.
    The vertex sets in both graphs are the same.  To construct the edge set,
    we pick a vertex $ v\in V $ and check if $ \{v,u\} \in E $ for every other $ u \in V $.
    We add those $ \{v, u\} \centernot\in E$ to the edge set of $ G^T $.
    $ \blacksquare $
    % paragraph Proof (end)

    \item
    We can follow a similar argument as in Question 1, part b and part c.  We first obtain the maximum
    cardinality $ m $ of a maximum independent set with binary search in $ O(\log_2 |V|) $.

    We now construct the solution to the functional problem.

    We create $ W \gets V $, and $ I \gets \emptyset $.
    We start by assigning $ w $ an arbitrary vertex in $ W $ that we have not picked before.
    We run our blackbox subroutine with
    vertex set $ W\backslash\{w\} $. If the answer is no, we know this vertex is an element
    of a maximum-cardinality independent set of $ G $.  If the answer is yes, we know that
    even when we remove this vertex, we can still obtain a maximum-cardinality independent
    set. Therefore, if the answer was yes, we assign $ W \gets W\backslash\{w\}$;  otherwise,
    $ W $ remains unchanged, and $ I \gets I\cup\{w\} $.
    We now pick another arbitrary $ w $ from $ W $ not yet picked, and repeat this process
    until we have tried every vertex in $ W $.

    \paragraph{Proof} % (fold)
    \label{par:Proof}
    We examine every vertex only once, and decide whether to include it or not
    in our solution after our blackbox subroutine returns an answer in $ O(1) $.
    Therefore, $ I $ is constructed in $ O(|V|) $ time.

    We have that any $ I \in [0, |V|]$.
    Originally, we have that $ W = V $,
    The proof that $ I $ indeed corresponds to a solution follows directly from our
    decision problem.  Every time we pick  $w  $, we will either remove it from
    $ W $, or keep it. We remove it if our subroutine told us that $ w $ was not
    necessary to construct maximum independent set from the set $ W\backslash\{w\} $.
    We keep it if the subroutine told us we could no longer obtain a maximum independent
    set by removing $ w $. Therefore, by the time the execution stops, we have examined
    every vertex in $ V $ and removed it or kept it in $ W $.  In the end, we have that $ W = I $,
    and so $ I $ is maximum.
    $ \blacksquare $
    % paragraph Proof (end)

    \item
    We claim that if $ G $ is connected, then the size of a maximum independent set $ I $
    is $ |I| =  \lfloor |V|/ 2 \rfloor $.  If $ G $ is not connected, then every vertex
    in some component is independent of any other vertex in any other component.

    Therefore, we find maximum independent sets for every component in $ G $, and
    obtain the maximum independent set $ I $ of  $ G $ by performing a union over all of them.

    To obtain the components of $ G $, we pick an arbitrary root $ s \in V$, and construct a
    BFS tree $ T $ of $ G $ rooted at $ s $.
    If not every vertex belongs to $T $, then we run BFS again with the remaining vertices,
    and an arbitrary root from the remaining vertices.
    We repeat this process until every $ v \in V $ is part of some BFS tree.

    We assume we use an adjacency list representation of the graph.
    The running time of this process is for the best case, calling BFS once, and for the worst
    case, calling BFS $ O(|V|) $ times. However, if we call it $ O(|V|) $ times, we know
    all the adjacency lists for all the vertices were empty, and so we can state the running time as
    just that of BFS $ O(|V| + |E|) $.

    For each component, we pick some leaf $ l $
    from the corresponding BFS tree, and include every vertex
    who is at an even distance from $ l $.
    Denote $ I_i $ to be the maximum independent set
    of some component $ C_i $.  Then we have $ I = \bigcup I_i$.  The time to construct each $ I_i $
    is linear in the size of the component $ C_i $, and the time to perform the union of all of them
    is linear in $ |V| $.  Therefore the running time of the whole algorithm is $ O(|V| + |E|) $.

    \paragraph{Proof} % (fold)
    \label{par:Proof}
    No vertex is indepedent of any other vertex it is adjacent too.  Therefore, if we
    have a connected graph, the maximum indepedent set has to necessarily be at most half
    the size of the vertex set for that connected component.  We take the floor to handle the
    cases for odd-valued vertex set cardinalities.

    That every vertex in some connected component
    is independent of every other vertex in a different connected component
    follows directly from the definition of connected components.

    We now show that picking we can pick any leaf $ l $ in a BFS tree to get $ I_i $ for component
    $ C_i $.  We know that with the constraint of $ d(x) \le 2 $ for any $ x \in V $, a tree
    can only have at most 2 leaves. Additionally, we know that either the connected component
    is a simple path, or it is a cycle.  If we have the case of a cycle, we can pick any arbitrary
    vertex $ u $ as part of our indepedenent set approximation, and add every vertex with even distance
    to $ u $.  If we have a simple path, then we necesarilly want to start from an endpoint
    to guarantee we obtain the maximum indepedent set following the same process.  In
    our BFS tree, picking a leaf $ l $ guarantees we start from this endpoint.
    In general, we only check for this case, because in the case of a cycle, we can still pick
    $ l $ since we can pick any $ v \in V $ as a starting point.
    $ \blacksquare $
    % paragraph Proof (end)

    \item
    We know that an upper bound for a maximum size independent set is the whole vertex set
    itself.  We also know that in a bipartite graph with vertex set $ V = V_1 \cup V_2 $,
    the lower bound for the size of a maximum indepedent set is the maximum of $ |V_1| $ and $ |V_2| $.


    \begin{prop}
        The cardinality of $ V $ is equal to the sum of
        cardinalities of a maximum independent set $ I $
        and a maximum matching $ M $ of $ G $.
    \end{prop}
    \paragraph{Proof} % (fold)
    \label{par:Proof}
        We start by assuming our bipartite graph has an empty edge set $ E $, and so $ |I| = |V| $.
        Now, consider $ |I| = |V| - 1 $.  Then this means there is at least one edge in $ E $ connecting
        a vertex $ v \in V_1 $ to some other vertex $ u \in V_2 $. Therefore, we cannot include
        this vertex $ v $ in $ I $ without having to remove $ u $ first.  Now consider
        $ |I| = |V| - 2 $.  We have the first case, and additionally a second edge connecting
        a different $ v^{\prime} \in V_1 $ to a different $ u^{\prime} \in V_2 $, and so
        the argument is similar for this pair of vertices.
        In general, we can have at most $ \min\{|V_1|,\;|V_2|\} $ such edges.
        These edges represent a maximum matching $ M $ in $ G $.
        Therefore, we have that
        \begin{align*}
            &&|I| &= |V| - |M|
            \\
            &&\Rightarrow \quad |V| &= |I| + |M|
        \end{align*}
    % paragraph Proof (end)
    Didn't have time to prove the construction of the actual set $ I $. The maximum can be obtained
    with the reduction of maximum matching from our previous assignment, to a maximum flow problem
    by adding a sink and a source.
\end{enumerate}
% section Independent Set (end)

%\end{spacing}
\end{document}