\documentclass[11pt]{article}
\usepackage[russian,greek,english]{babel}
\usepackage{amsmath,ifthen,color,eurosym}
\usepackage{wrapfig,hyperref,cite}
\usepackage{latexsym,amsthm,amsmath,amssymb,url,cite}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{stmaryrd,wasysym}
\usepackage{colortbl}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}

\def\baselinestretch{1}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{observation}{Observation}
\newtheorem{proposition}{Proposition}

\setlength{\textheight}{22cm}
\setlength{\topmargin}{-1cm}
\setlength{\textwidth}{165mm}
\setlength{\oddsidemargin}{-3mm}
\setlength{\unitlength}{1mm}


%\renewcommand{\refname}{\small References}
\addto{\captionsenglish}{\renewcommand{\refname}{\normalsize
    References}}



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
%Put here the package you need, new commands, ...



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%

\begin{document}
%1 page max !! 

%Write your title here: 
\noindent{\bf\Large Constructive algorithm for path-width of matroids}

%List the authors as follows (you may underline the speaker, or just
%name the speaker, and mention your co-authors at the end, up to you):  
\noindent Jisu Jeong -- {\small KAIST}

\noindent Eun Jung Kim -- {\small LAMSADE}

\noindent \underline{Sang-il Oum} -- {\small KAIST}



\vspace{2ex}

\noindent{\bf Abstract:} %Here write your abstract
Given $n$ subspaces of a finite-dimensional vector space over a fixed finite field $\mathbb F$, we wish to find a linear layout $V_1,V_2,\ldots,V_n$ of the subspaces such that $\dim((V_1+V_2+\cdots+V_i) \cap (V_{i+1}+\cdots+V_n))\le k$ for all $i$; 
such a linear layout is said to have width at most $k$. 
When restricted to $1$-dimensional subspaces, this problem is equivalent to computing the path-width of an $\mathbb F$-represented matroid in matroid theory and computing the trellis-width (or minimum trellis state-complexity) of  a linear code in coding theory. 
  
  We present a fixed-parameter tractable algorithm to construct a
  linear layout of width at most $k$,  if it exists, for input
  subspaces of a finite-dimensional vector space over $\mathbb F$. As
  corollaries, we obtain 
  \begin{itemize}
  \item a fixed-parameter tractable algorithm to produce a
    path-decomposition of width at most $k$ for an input $\mathbb
    F$-represented matroid of path-width at most $k$, and 
  \item a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most $k$ for an input graph of linear rank-width at most $k$.
  \end{itemize}
In both corollaries, no such algorithms were known previously.
Our approach is based on dynamic programming combined with the idea developed by Bodlaender and Kloks (1996) for their work on path-width and tree-width of graphs. 

It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width; a theorem by Geelen, Gerards, and Whittle~(2002) implies that for each fixed finite field $\mathbb F$, there are finitely many forbidden $\mathbb F$-representable minors for the class of matroids of path-width at most $k$. An algorithm by Hlin{\v e}n{\'y} (2006) can detect a minor in an input $\mathbb F$-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition even if the complete list of forbidden minors were known. 
Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

\end{document}