Here is one slow possibility. You can cast the problem as a linear programming problem, with a vector consisting of indicator variables for the edges and vertices. Let the vector be: $(e_1, .., e_m, v_1, .., v_n)$ where there are $m = |E_G|$ edges and $n = |V_G|$ vertices in the graph. Then the graph has $d_G = 2 |E_G| / |V_G| $. Now, a subgraph $H$ will have $d_H = 2 |E_H| / |V_H|$. Then, we have:
$$|E_G| |V_H| - |E_H| |V_G| = d_G |V_G| |V_H|/2 -d_H |V_G| |V_H|/2 = (|V_G| |V_H|/2) ( d_G - d_H)$$
The sign of the minimum over all subgraphs $H$ of $|E_G| |V_H| - |E_H| |V_G|$ will determine whether the graph is unbalanced, balanced or strictly balanced.
The LinearProgramming
constraints come from each vertex in the graph: if the vertex is not in the subgraph, then the associated edges must be absent from the subgraph. Here is the function:
balanceQ[g_] := Module[
{e=EdgeList[g], ec=EdgeCount[g], v=VertexList[g], vc=VertexCount[g], res},
res = Quiet[
LinearProgramming[
Join[
-vc Table[1, {ec}],
ec Table[1, {vc}]
],
Join[
Table[
With[{b = Boole[Not@*FreeQ[v[[i]]] /@ e]},
Join[b, PadRight[{-Total[b]}, vc, 0, {i-1}]]
],
{i, vc}
],
{
Join[Table[0, {ec}], Table[1, {vc}]],
Join[Table[0, {ec}], Table[1, {vc}]]
}
],
Join[
Table[{0, -1}, {vc}],
{
{1, 1}, (* at least one vertex *)
{vc-1,-1} (* not all vertices *)
}
],
Table[{0, 1}, {vc+ec}],
Integers
],
LinearProgramming::lpip
];
Switch[Sign[-vc Total[res[[;;ec]]] + ec Total[res[[ec+1;;]]]],
-1, "Unbalanced",
0, "Balanced",
1, "Strictly balanced"
]
]
As an example, consider graphs from GraphData
:
g = GraphData /@ GraphData[30];
SortBy[AbsoluteTiming[balanceQ[#]]& /@ g, First]
{{0.001414, "Balanced"}, {0.002054, "Unbalanced"}, {0.002168,
"Unbalanced"}, {0.002208, "Balanced"}, {0.024167, "Unbalanced"}, {0.043445,
"Unbalanced"}, {0.049372, "Strictly balanced"}, {0.069279,
"Balanced"}, {0.083165, "Strictly balanced"}, {0.086195,
"Strictly balanced"}, {0.094856, "Strictly balanced"}, {0.100238,
"Balanced"}, {0.103429, "Strictly balanced"}, {0.110622,
"Strictly balanced"}, {0.123556, "Strictly balanced"}, {0.133809,
"Strictly balanced"}, {0.138439, "Strictly balanced"}, {0.157034,
"Strictly balanced"}, {0.195019, "Strictly balanced"}, {0.226968,
"Strictly balanced"}, {0.237197, "Strictly balanced"}, {0.267112,
"Strictly balanced"}, {0.267291, "Strictly balanced"}, {0.322829,
"Strictly balanced"}, {0.327068, "Strictly balanced"}, {0.333683,
"Strictly balanced"}, {0.344322, "Strictly balanced"}, {0.352541,
"Strictly balanced"}, {0.373047, "Strictly balanced"}, {0.384115,
"Strictly balanced"}, {0.411243, "Strictly balanced"}, {0.423324,
"Strictly balanced"}, {0.433958, "Strictly balanced"}, {0.443956,
"Strictly balanced"}, {0.448159, "Strictly balanced"}, {0.460425,
"Strictly balanced"}, {0.47054, "Strictly balanced"}, {0.479184,
"Strictly balanced"}, {0.485696, "Strictly balanced"}, {0.502723,
"Strictly balanced"}, {0.51482, "Strictly balanced"}, {0.528539,
"Strictly balanced"}, {0.536904, "Strictly balanced"}, {0.538585,
"Strictly balanced"}, {0.546364, "Strictly balanced"}, {0.55003,
"Strictly balanced"}, {0.614187, "Balanced"}, {0.709653,
"Strictly balanced"}, {0.710389, "Unbalanced"}, {0.742609,
"Strictly balanced"}, {0.781095, "Strictly balanced"}, {0.885017,
"Strictly balanced"}, {0.925772, "Strictly balanced"}, {1.1346,
"Strictly balanced"}, {1.21853, "Strictly balanced"}, {1.30096,
"Balanced"}, {1.32248, "Strictly balanced"}, {1.3259,
"Strictly balanced"}, {1.33169, "Strictly balanced"}, {1.49999,
"Strictly balanced"}, {1.77298, "Strictly balanced"}, {2.14196,
"Strictly balanced"}, {2.19037, "Strictly balanced"}, {2.26871,
"Strictly balanced"}, {2.33642, "Strictly balanced"}, {2.49905,
"Strictly balanced"}, {2.58194, "Strictly balanced"}, {2.58368,
"Strictly balanced"}, {2.70069, "Strictly balanced"}, {2.86718,
"Strictly balanced"}, {2.86911, "Strictly balanced"}, {2.87815,
"Strictly balanced"}, {2.90138, "Strictly balanced"}, {3.24567,
"Strictly balanced"}, {3.4512, "Strictly balanced"}, {4.92757,
"Strictly balanced"}, {4.95015, "Strictly balanced"}, {4.9556,
"Strictly balanced"}, {5.0526, "Strictly balanced"}, {5.05777,
"Strictly balanced"}, {5.25303, "Strictly balanced"}, {5.51572,
"Strictly balanced"}, {5.93311, "Strictly balanced"}, {7.65476,
"Strictly balanced"}, {8.4197, "Strictly balanced"}, {9.07264,
"Strictly balanced"}, {9.89535, "Strictly balanced"}, {10.352,
"Strictly balanced"}, {11.3917, "Strictly balanced"}, {151.473,
"Strictly balanced"}, {215.75, "Strictly balanced"}}
Even for graphs with 30 vertices, the timing for balanceQ
ranges from .001 to 215, so it is very slow, but should be much faster than checking $|E_H|/|V_H|$ for all 2^30 subgraphs.