\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 subsequene 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-gree 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 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 endpoins to be the color of the merged vertex, (b) remove a vertex, (c) remove an edge. $\GM(n)$ is 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. You may use the GMT. \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 subtlely 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}