\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{url}
\usepackage{amsmath}

% This is a file of macros and definitions that may come up in
% ANY LATEX paper.  Typically I'll use this file and some other file in the
% directory of the paper, this one for general math things, that one for
% things specific to that paper.
%
% font's used and general paper things.
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\eightrm=cmr8
\font\sevenrm=cmr7
% \font\title=cmbx10 scaled \magstep1 % extra big title font
\font\ss=cmss10 % used by \proof
\font\smallcaps=cmcsc10 % used to label Theorems, etc.
% imhibit black bars on overflows
%
\overfullrule=0pt
%
% today's date
%
%
% English words that I always italizice in papers.
% Some words that appear in math mode alot that I wasn roman
%

\newcommand{\SUBSEQ}{{\rm SUBSEQ}}
\newcommand{\minor}{{\preceq_m}}
\newcommand{\minorp}{{\preceq_m'}}
\newcommand{\cminor}{{\preceq_{\rm c\hbox{-}m}}}
\newcommand{\GM}{{\rm  GM}}
\newcommand{\TREE}{{\rm  TREE}}
\newcommand{\R}{\rm  R} 
\newcommand{\B}{\rm  B} 
\newcommand{\G}{\rm  G} 
\newcommand{\Y}{\rm  P} 

\newcommand{\IO}{\exists^\infty}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\newcommand{\into}{{\rightarrow}}
\newcommand{\D}{{\sf D}}
\newcommand{\N}{{\sf N}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\reals}{{\sf R}}
\newcommand{\qd}{{\rm qd}}
\newcommand{\GE}[1]{{\equiv^{G}_{#1}}}
\newcommand{\TE}[1]{{\equiv^{T}_{#1}}}
\newcommand{\TES}[1]{{\equiv^{T}_{#1,{\rm S}}}}
\newcommand{\TEB}[1]{{\equiv^{T}_{#1,{\rm BOOL(S)}}}}
\newcommand{\LL}{{\cal{L}}}
\newcommand{\onepe}{1+\epsilon}
\newcommand{\oneme}{1-\epsilon}
\newcommand{\cool}{cool}
\newcommand{\nze}{numzeros}
\newcommand{\non}{numones}
\newcommand{\LR}[2]{ {\rm LR}_{{#2}}({#1})}
\newcommand{\LH}[2]{ {\rm LH}({#1};{#2})}
\newcommand{\bbb}{{\gamma}}
\newcommand{\COL}{{\rm COL}}
\newcommand{\card}[1]{\#(#1)}
\newcommand{\st}{\mathrel{:}}
\newcommand{\fhat}{{\hat{f}}}
\newcommand{\Ahat}{{\hat{A}}}

\begin{document}

\centerline{\bf Homework 05, Morally Due 12:30PM, Tue Mar 03  2026}


\newif{\ifshowsoln}
%\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}

\item
(0 points) What is your name? 


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage


\item
(35 points)
Let $\Sigma=\{a,b\}$. 
Let $\Sigma^*$ be the set of all strings over $\Sigma$ including the empty string

(Example: $aabba$,  $bababbba$.)

If $x,y\in\Sigma^*$ then $x$ is a {\it subsequence of} $y$ if
you can take $y$, remove some letters, and get $x$.

Example:  $abba$ is a subsequence of $aababaabaaaabaa$

We define $x\preceq y$ to mean that $x$ is a subsequence of $y$. 

Show that $(\Sigma^*,\preceq)$ is a well quasi order by using a 
minimal bad sequence argument. 

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(0 point but you must do this to appreciate what I tell you when I go over
the subsequence problem in class. Do not hand anything in for this problem.) 

If $w\in\Sigma^*$ then $\SUBSEQ(w)$ is the set of all subsequences of $w$. 

Let $L\subseteq \{a,b\}^*$. Then $\SUBSEQ(L) = \cup_{w\in L} \SUBSEQ(w)$. 

\begin{enumerate}
\item 
Look at these two slide packets from my CMSC 452, on regular languages. 

\url{https://www.cs.umd.edu/~gasarch/COURSES/452/S25/slides/dfatalk.pdf}

\url{https://www.cs.umd.edu/~gasarch/COURSES/452/S25/slides/nfatalk.pdf}

Using the DFA NFA equivalence show the following:

\bigskip

{\it If $L$ is regular then $\SUBSEQ(L)$ is regular. }

\bigskip

\item 
Look at this two slide packets from my CMSC 452, on context free languages. 
(Only need up to around slide 23---the definitions of a context free grammar
and of a context free language.) 

{\it \url{https://www.cs.umd.edu/~gasarch/COURSES/452/S25/slides/cfgtalk.pdf}}

Using the definition of context-free grammar show the following: 

\bigskip

{\it If $L$ is a context-free language then $\SUBSEQ(L)$ is a context-free language.}

\bigskip

\item
I assume you all know what P is, the set of languages in polynomial time.

Is the following TRUE, FALSE, or UNKNOWN TO SCIENCE:

\bigskip

{\it If $L$ is in P then $\SUBSEQ(L)$ is in P.}

\bigskip

\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(35 points) 
For this problem I define the  minor ordering on colored graphs.
$H\cminor G$, as follows:
$H\cminor G$ if you can take $G$ and, by a sequence
of the following operations, obtain $H$:
(a) contract an edge and choose one of the colors of the endpoints to be the
color of the merged vertex, 
(b) remove a vertex, 
(c) remove an edge.

For this problem you can assume the GMT for COLORED graphs:

{\it Let $n\in\N$. If $G_1,G_2,\ldots,$ is an infinite sequence of $n$-colored graphs
then there exists $i<j$ such that $G_i\cminor G_j$.} 

Let $\GM(n)$ be the largest number such that there exists a bad sequence (using $\cminor)$) 
of $n$-colored  graphs

$G_1, G_2,\ldots,G_{\GM(n)}$ 

where $G_i$ has at most $i$ vertices. 

Show that $\GM(n)$ exists.

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(30 points)
Fix $k\in\N$.
Assume that, for all $1\le i\le k$, WE HAVE an FPT algorithm for 

$VC_i = \{ G \colon G\hbox{ has a vertex cover of size $\le i$} \}$. 

(Recall that this means we really have the code.) 

Prove that WE HAVE an FPT algorithm for the following FUNCTION:

On input $G=(V,E)$:

\begin{itemize}
\item 
If $G\notin VC_k$ then output NO.
\item
If $G\in VC_k$ then output YES and ALSO output a vertex cover $U\subseteq V$
of size $\le k$. 
\end{itemize}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage




\item
(0 points. Do for your own enlightenment. DO NOT hand in.) 

Let $(X,\preceq)$ be a wqo. 
$2^{{\rm fin} X}$ is the set of finite subsets of $X$.

We define the following ordering on $2^{{\rm fin} X}$ 

$A\preceq_1 B$ if there exists a 1-1 function $f\colon A\into B$
such that $x\preceq f(x)$. 

Note that $\preceq_1$ is defined using $\preceq$. 

Show that 
$(2^{{\rm fin} X},\preceq_1)$ is a wqo.

{\bf Hint:} This is an adjustment of the proof that 
$2^{{\rm fin} \N}$ under a similar ordering is a wqo.

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage


\item
(Extra Credit)

I first discuss the subtlety about the Kruskal Tree Theorem
that I alluded to in class.

I defined the minor ordering, denoted $H\minor G$, as follows:
$H\minor G$ if you can take $G$ and, by a sequence
of the following operations, obtain $H$:
(a) contract an edge.
(b) remove a vertex, 
(c) remove an edge.

Here is what I stated in class which, while true,
is not what you should try to prove:

STATEMENT A: {\it The set of trees under $\minor$ is a wqo.}

DO NOT try to prove STATEMENT A. 
It is true; however, to prove it you need to prove something {\it stronger}.
This is one of those cases where it is easier to prove a stronger theorem.

I now define the minor' ordering, denoted $H\minorp G$, as follows:
$H\minorp G$ if you can take $G$ and, by a sequence
of the following operations, obtain $H$:
(a) contract an edge. Oh. Just one operation. 

Here is what you can prove similar to the other proofs:

STATEMENT B: {\it The set of trees under $\minorp$ is a wqo.}

For the extra credit prove STATEMENT B.
ALSO (and this is probably the only part I will look at)
\begin{enumerate}
\item 
State clearly which part of the proof breaks down if 
you use $\minor$ instead of $\minorp$.
\item 
State clearly which part of the proof breaks down if 
you use SUBGRAPH instead of $\minorp$.
\end{enumerate}

\end{enumerate}
\end{document}

