\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 Polynomial Fixed-Parameter Algorithms: \\
A Case Study for Longest Path on Interval Graphs}

%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 George B.~Mertzios -- {\small Durham University}




\vspace{2ex}

\noindent{\bf Abstract:} %Here write your abstract

We study the design of fixed-parameter algorithms for problems already known
to be solvable in polynomial time. The main motivation is to get more
efficient algorithms for problems with unattractive polynomial running
times. Here, we focus on a fundamental graph problem: \textsc{Longest Path};
it is NP-hard in general but known to be solvable in $O(n^{4})$~time on $n$%
-vertex interval graphs. We show how to solve \textsc{Longest Path on
Interval Graphs}, parameterized by vertex deletion number~$k$ to proper
interval graphs, in $O(k^{9}n)$ time. Notably, \textsc{Longest Path} is
trivially solvable in linear time on proper interval graphs, and the
parameter value~$k$ can be approximated up to a factor of~4 in linear time.
From a more general perspective, we believe that the idea of using
parameterized complexity analysis for polynomial-time solvable problems
offers a very fertile ground for future studies for all sorts of algorithmic
problems. It may enable a refined understanding of efficiency aspects for
polynomial-time solvable problems similarly to what classical parameterized
complexity analysis does for NP-hard problems.\newline

This work has been co-authored by Archontia C.~Giannopoulou (University of Warsaw) and Rolf Niedermeier (TU Berlin).

\end{document}