The Small Set Vertex Expansion Problem

Abstract

Given a graph G=(V,E) , the vertex expansion of a set S⊂V is defined as ΦV(S)=|N(S)

S|. 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)|k ; equivalently minimizing |N(S)|. SSVE 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. Using the hardness of Minimum k-Union problem, we prove that Small Set Vertex Expansion problem is 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 k, (2) the problem is fixed-parameter tractable (FPT) when parameterized by the neighbourhood diversity nd, and (3) it is fixed-parameter tractable (FPT) when parameterized by treewidth tw of the input graph.