  Given a set of vertices in a network, that we believe are of interest for the
application under analysis, community search is the problem of producing a
subgraph potentially explaining the relationships existing among the vertices
of interest. In practice this means that the solution should add some vertices
to the query ones, so to create a connected subgraph that exhibits some
"cohesiveness" property. This problem has received increasing attention in
recent years: while several cohesiveness functions have been studied, the bulk
of the literature looks for a solution subgraphs containing all the query
vertices. However, in many exploratory analyses we might only have a reasonable
belief about the vertices of interest: if only one of them is not really
related to the others, forcing the solution to include all of them might hide
the existence of much more cohesive and meaningful subgraphs, that we could
have found by allowing the solution to detect and drop the outlier vertex. In
this paper we study the problem of community search with outliers, where we are
allowed to drop up to $k$ query vertices, with $k$ being an input parameter. We
consider three of the most used measures of cohesiveness: the minimum degree,
the diameter of the subgraph and the maximum distance with a query vertex. By
optimizing one and using one of the others as a constraint we obtain three
optimization problems: we study their hardness and we propose different exact
and approximation algorithms.
