\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, ...

\newcommand{\CSP}{CSP}
\newcommand{\MCSP}{MAXCSP}
\newcommand{\SAT}{CNFSAT}


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

\begin{document}
%1 page max !! 

%Write your title here: 
\noindent{\bf\Large Complexity and  Approximability for Parameterized \CSP s}

%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 H. Dell -- {\small Saarland University and Cluster of Excellence, Saarbr\"{u}cken},
\noindent E. J. Kim -- {\small Université Paris Dauphine},
\noindent M. Lampis -- {\small Université Paris Dauphine},
\noindent \underline{V. Mitsou} -- {\small SZTAKI, Hungarian Academy of Sciences, Budapest},
\noindent T. M\"omke -- {\small Saarland University, Saarbr\"{u}cken}.


\vspace{2ex}

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

%This paper is about ... Cite like that \cite{CCHPP}, \cite{Wol15}. 

\textsc{Constraint Satisfaction Problems} (\CSP s) play a central role in almost all
branches of theoretical computer science. Starting from \SAT, the prototypical NP-complete problem, 
the computational complexity of \CSP s has been widely
studied from various points of view. In this paper we focus on two aspects of
\CSP\ complexity which %though well-investigated, 
have mostly been
considered separately so far in the literature: parameterized complexity and
approximability. We study four standard predicates and contribute some of the 
first results in this joint area.
%, indicating that the point of view of approximability considerably
%enriches the parameterized complexity landscape of \CSP s.

%state of the art: parameterized

\paragraph{Parameterized \CSP s.} The vast majority of interesting \CSP s
are NP-hard  \cite{S78}. This has motivated the study of such problems from a
parameterized complexity point of view, and indeed this topic has attracted
considerable attention in the literature \cite{G06}. 
In this paper we focus on \emph{structurally} parameterized \CSP s, that is, we
consider \CSP s where the parameter is some measure of the structure of the
input instance.  The central idea behind this approach is to represent the
structure of the \CSP\ using a (hyper-)graph and leverage the powerful tools
commonly applied to parameterized graph problems (such as tree decompositions)
to solve the \CSP. %The typical goal of this line of research is to find the most general
%parameterization of a \CSP\ that still remains fixed-parameter tractable (FPT).
%To give a concrete example for a very well-known \CSP, \SAT\ is FPT when
%parameterized by the treewidth of its incidence graph but it is W-hard for more general
%parameters such as clique-width \cite{OPS13}. %General (boolean) \CSP\ on the other hand is 
%already W[1]-hard parameterized by the incidence treewidth \cite{S13a}. Thus,
%parameterized investigations aim to locate the boundary where a \CSP\ jumps from
%being FPT to being W-hard. 
%The next natural question of course is how we can deal with the W-hard cases of a \CSP\ once they are identified.

%state of the art: approximation

\paragraph{Approximation.} \CSP s also play a central role in the theory
of (polynomial-time) approximation. In this context we
typically consider a \CSP\ as an optimization problem (\MCSP) where the goal is
to find an assignment to the variables that satisfies as many of the
constraints as possible. Unfortunately, essentially all non-trivial \CSP s are
hard to approximate (APX-hard) %from this point of view 
\cite{KSW97}. 
%Thus, research in this area typically focuses on discovering
%the best approximation ratio that can be achieved in polynomial time.
%Amazingly, for many natural \CSP s this happens to be exactly the ratio achieved
%by a completely random assignment \cite{H01}. 
This motivates the question of whether we can find %natural 
cases where %non-trivial 
efficient approximations are possible.

%parameterized approximation: motivation

\paragraph{Results.} We consider four different types of
\CSP s with %where the constraints are respectively 
\emph{or}, \emph{and}, \emph{parity} and \emph{majority} constraints respectively. %functions. 
The new ingredient in our approach is that, in addition to trying to determine
which parameters make a \CSP\ FPT or W-hard, we also ask if the optimization
versions of W-hard cases can be well-approximated. We show that %already 
these basic
predicates display a diverse set of behaviors, ranging from being FPT to optimize exactly (parity), to being
W-hard but well-approximable (or, majority), to being W-hard and inapproximable (and). Our results indicate that 
the point of view of approximability considerably enriches the parameterized complexity landscape of \CSP s.

%If you need a ref section, do it more or less like that : 
\small
\begin{thebibliography}{1}

\bibitem{G06}
M.~Grohe.
\newblock The structure of tractable constraint satisfaction problems.
\newblock In R.~Kralovic and P.~Urzyczyn, editors, {\em {MFCS} 2006,
  Star{\'{a}} Lesn{\'{a}}, Slovakia, August 28-September 1, 2006, Proceedings},
  volume 4162 of {\em Lecture Notes in Computer Science}, pages 58--72.
  Springer, 2006.

%\bibitem{H01}
%J.~H{\aa}stad.
%\newblock Some optimal inapproximability results.
%\newblock {\em J. {ACM}}, 48(4):798--859, 2001.

\bibitem{KSW97}
S.~Khanna, M.~Sudan, and D.~P. Williamson.
\newblock A complete classification of the approximability of maximization
  problems derived from boolean constraint satisfaction.
\newblock In F.~T. Leighton and P.~W. Shor, editors, {\em Proceedings of the
  Twenty-Ninth Annual {ACM} Symposium on the Theory of Computing, El Paso,
  Texas, USA, May 4-6, 1997}, pages 11--20. {ACM}, 1997.

%\bibitem{OPS13}
%S.~Ordyniak, D.~Paulusma, and S.~Szeider.
%\newblock Satisfiability of acyclic and almost acyclic {CNF} formulas.
%\newblock {\em Theor. Comput. Sci.}, 481:85--99, 2013.

%\bibitem{samer2010constraint}
%M.~Samer and S.~Szeider.
%\newblock Constraint satisfaction with bounded treewidth revisited.
%\newblock {\em J. Comput. Syst. Sci.}, 76(2):103--114, 2010.

\bibitem{S78}
T.~J. Schaefer.
\newblock The complexity of satisfiability problems.
\newblock In R.~J. Lipton, W.~A. Burkhard, W.~J. Savitch, E.~P. Friedman, and
  A.~V. Aho, editors, {\em Proceedings of the 10th Annual {ACM} Symposium on
  Theory of Computing, May 1-3, 1978, San Diego, California, {USA}}, pages
  216--226. {ACM}, 1978.

%\bibitem{S13a}
%S.~Szeider.
%\newblock Not so easy problems for tree decomposable graphs.
%\newblock {\em CoRR}, abs/1107.1177, 2011.

\end{thebibliography}


\end{document}