%Compiler avec pdflatex, le rÃ©sultat ne doit pas dÃ©passer une page
%Merci de respecter scrupuleusement ce modÃ¨le.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}

\newcommand{\I}{{\rm I}}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{F. Fioravantes and N. Melissinos and T. Triommatis: Complexity of Finding Maximum Locally Irregular Induced Subgraphs}
%
% Pour le sommaire
\addcontentsline{toc}{section}{F. Fioravantes and N. Melissinos and T. Triommatis: Complexity of Finding Maximum Locally Irregular Induced Subgraphs}
%

% Pour la liste des auteurs
\index{Fioravantes, F.}\index{Melissinos, N.}\index{Triommatis, T.}
%

% Citer un par un les auteurs et leur affiliation
Foivos Fioravantes, Universit\'e C\^ote d'Azur, Inria, CNRS, I3S, Valbonne, France
{\tt foivos.fioravantes@inria.fr}\\
\indent
\underline{Nikolaos Melissinos}, Universit\'e Paris-Dauphine,  PSL Research University, CNRS, UMR 7243, LAMSADE, Paris,
{\tt nikolaos.melissinos@dauphine.eu} \\
\indent
Theofilos Triommatis, School of Electrical Engineering, Electronics and Computer Science University of Liverpool, Liverpool,\\
{\tt Theofilos.Triommatis@liverpool.ac.uk	}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le rÃ©sumÃ©



A graph $G$ is said to be \emph{locally irregular}, if every two adjacent vertices of $G$ have different degrees. The notion of locally irregular graphs was first introduced in~\cite{BBPW15}. In this work, we introduce and study the problem of finding a largest locally irregular induced subgraph of a given graph. This problem is equivalent to identifying what is the minimum number $\I(G)$ of vertices that must be deleted from $G$, so that what remains is a locally irregular graph.


We first treat some easy graph families, namely paths, cycles, trees, complete bipartite and complete graphs. In addition, we show that the decision version of the introduced problem is NP-Complete even for subcubic bipartite graphs. 

Then, we decide to study the parameterized complexity of the problem. In particular, we provide two algorithms that compute $\I(G)$. The first one considers the size of the solution $k$ and the $\Delta$ of $G$ as parameters and has running time $(2\Delta)^kn^{\mathcal{O}(1)}$, while the second one considers the treewidth $tw$ and $\Delta$ of $G$, and has running time $\Delta^{2tw}n^{\mathcal{O}(1)}$. 
Finally, we show that these algorithms are essentially optimal as we prove that there is no algorithm that computes $\I(G)$ with dependence $f(k)n^{o(k)}$ or $f(tw)n^{o(tw)}$, unless the ETH fails.\\



\begin{thebibliography}{99}
\bibitem{BBPW15}
O.~Baudon and J.~Bensmail and J.~Przybyło and M.~Wozniak, \emph{On decomposing regular graphs into locally irregular subgraphs}, Eur. J. of Comb, {\bf 49} (2015), 90--104.
\end{thebibliography}



\vfill
\end{document}
