The Small Set Vertex Expansion Problem.

• Small Set Vertex Expansion is W[1]-hard when parameterized by the solution size. • Small Set Vertex Expansion is FPT when parameterized by neighbourhood diversity of the input graph. • Small Set Vertex Expansion can be solved in polynomial time for graphs of bounded clique-width. • Small Set Vertex Expansion is FPT when parameterized by treewidth of the input graph. In the Small Set Vertex Expansion (SSVE) problem, we are given a graph G = (V , E) and a positive integer k ≤ | V (G) | 2 , the goal is to return a set S ⊂ V (G) of k nodes minimizing the vertex expansion Φ V (S) = | N (S) |. The Small Set Vertex Expansion problem has not been as well studied as its edge-based counterpart Small Set Expansion (SSE). SSE, and SSVE to a less extend, have been studied due to their connection to other hard problems including the Unique Games Conjecture and Graph Colouring. The Small Set Vertex Expansion is known to be NP-complete. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[1]-hard when parameterized by the solution size, (2) the problem is fixed-parameter tractable (FPT) when parameterized by the neighbourhood diversity of the input graph, (3) it can be solved in polynomial time for graphs of bounded clique-width, and (4) it is fixed-parameter tractable (FPT) when parameterized by treewidth of the input graph. [ABSTRACT FROM AUTHOR]