Computing the isoperimetric number of a graph (Q1905161)

Let \(G\) be a finite graph. Denote by \(\partial X\), where \(X \subset VG\), the set of edges of the graph \(G\) with one end in \(X\) and the other end in the set \(VG \backslash X\). The ratio \(i(G) = \min |\partial X|/ |X |\), where the minimum is over all nonempty subsets \(X\) of the set \(VG\) such that \(|X |\leq |VG |/2\), is called the isoperimetric number of the graph \(G\). It is easy to see that the isoperimetric number may be used as a ``measure of connectivity'' of the graph. The problem of determining the isoperimetric number is clearly linked with graph partition problems, which often arise in various applications. The isoperimetric number is also important for studying Riemann surfaces. These and other applications of the isoperimetric number justify the analysis of graphs of this kind. The properties of the isoperimetric number are presented in more detail in [(*) \textit{B. Mohar}, J. Comb. Theory, Ser. B 47, No. 3, 274-291 (1989; Zbl 0719.05042)]. A similar construct for infinite graphs has been considered in other papers. It is shown in (*) that the computation of the isoperimetric number is an NP-hard problem for graphs with multiple edges. We show that the decision problem ``given the graph \(G\) and two integers \(s\) and \(t\) decide if \(i(G) \leq s/t\)'' is NP-complete even for simple graphs with vertex degrees not exceeding 3. Note that the isoperimetric number of a tree can be computed by a known polynomial-time algorithm, see the Mohar paper mentioned above.