
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
Description
We generalize the seminal Graph Minor algorithm of Robertson and Seymour to the parity
version. We give polynomial time algorithms for the following
problems:
\begin{enumerate}
\item
the parity $H$minor (Odd $K_k$minor) containment problem, and \item
the disjoint paths problem with $k$ terminals and the parity condition for each path,
\end{enumerate}
as well as several other related problems.
We present an $O(m \alpha(m,n) n)$ time algorithm for these problems
for any fixed $k$, where $n,m$ are the number of vertices and the
number of edges, respectively, and the function $\alpha(m,n)$ is the
inverse of the Ackermann function (see Tarjan \cite{tarjan}).
Note that the first problem includes the problem of testing whether
or not a given graph contains $k$ disjoint odd cycles (which was
recently solved in \cite{tony,oddstoc}), if $H$ consists of $k$ disjoint triangles. The algorithm for the
second problem generalizes the Robertson Seymour algorithm for the $k$disjoint paths problem.
As with the RobertsonSeymour algorithm for the $k$disjoint paths problem for any fixed $k$,
in each iteration, we would like to either use the presence of a huge clique minor, or alternatively exploit the
structure of graphs in which we cannot find such a minor. Here, however, we must
take care of the parity of the paths and can only use an ``odd clique minor". This requires new techniques to describe the structure of the graph when we cannot find such a minor.
We emphasize that our proof for the correctness of the above
algorithms does not depend on the full power of the Graph Minor
structure theorem \cite{RS16}. Although the original Graph Minor algorithm of Robertson and Seymour
does depend on it and our proof does have similarities to their arguments, we can avoid
the structure theorem by building on the shorter proof for the
correctness of the graph minor algorithm in \cite{kw}. Consequently, we are able to avoid the much of the
heavy machinery of the Graph Minor structure theory. Our proof is less than 50 pages.