Suppose $G$ is a graph. $E(G)$ and $V(G)$ denote the sets of the edges and nodes (vertices) of $G$, respectively.
I need a spanning subgraph of $G$ (let’s call the subgraph $g$). The subgraph must be both connected and radial (acyclic like a tree). The topic of connectivity has already been well discussed here (Ensure a graph is connected in a linear programming problem) and I will briefly discuss it here before I go over my major question.
To formulate the connectivity constraint, I use the flow of a phantom commodity. All the nodes of the original graph must be retained in the subgraph. Assume the graph is undirected with $|V(G)|=n$. In what follows I will assume that if $(i,j)$ is an edge, $(j,i)$ is recognized as the same edge and the variable $x_{ji}$ exist (and is constrained to equal $x_{ij}$). $x_{ij}$ is a binary variable representing the status of the edge connecting node $i$ to $j$. If $x_{ij}$ is zero then the edge $(i,j)$ is removed. Arbitrarily pick one vertex $υ_0\in V(G)$ as the source, with a supply of $n-1$ units of the phantom commodity. Every other vertex has demand $1$. Add variables $y_{ij}$, representing the flow of whatever it is from $i$ to $j\neq i$ across the edge between them, together with the below constraints:
$$-(n-1)x_{ij}\le y_{ij}\le (n-1)x_{ij}, \quad \forall\ i,j\in V(G),\ i\neq j \tag 1$$
$$\sum_{j\in V:(v_0,j)\in E(G)}y_{v_0,j} = n-1, \tag 2$$
and
$$\sum_{j:(i,j)\in E(G)}y_{i,j}=\sum_{j:(j,i)\in E(G)}y_{j,i}-1,\quad \forall\ i\in V(G)\backslash \lbrace v_0 \rbrace. \tag 3$$
The first constraint essentially says that you cannot move the commodity across an edge that was not chosen for the subgraph. The second constraint dictates the flow out of the chosen source vertex (and serves to ensure that it is connected to the rest of the subgraph). The third constraint says that at every other node, one unit of supply gets absorbed and anything left gets passed along. The approach I use for representing the radiality of the subgraph is to model the network as a directed graph. The clear statement of the constraints is as follows:
$$B_{ij}+B_{ji}=x_{ij},\ (i,j)\in E(G) \tag 4$$
$$\sum_{j\in N_i}B_{i,j}=1,\ i=2,3,\ldots,n \tag 5$$
$$B_{1j}=0,\ j\in N_1 \tag 6$$
$$B_{ij}\in\{0,1\},\ (i,j)\in E(G) \tag 7$$
The above-explained methodologies for modeling the connectivity and radiality constraints are well-known and work very well. There also exists an alternative method for modeling the radiality. In this method they use the following formula instead of the above-explained radiality constraints (i.e., eqs. (4)-(7)).
$$\sum_{(i,j)\in E(G)}x_{ij} = |V(G)|-1 \tag 8$$
Eq. (8) states that the number of the edges of the spanning subgraph must be equal to the number of the nodes of the original graph minus one.
When I use eqs. (1)-(3) (for connectivity) and eqs. (4)-(7) (for radiality), the model executes quite fast; however, when I use eqs. (1)-(3) (for connectivity) and eq. (8) (for radiality), the model becomes exponentially slow as the number of nodes (or edges) increases. Both will give the same results though. I’m wondering what is causing such a huge difference in terms of computation time. Is it because the number of feasible solutions from the perspective of the eqs. (4)-(7) is very different from that of eq. (8)? How can I compute the number of feasible subgraphs given by eqs. (4)-(7) and eq. (8)? I know that the number of feasible combinations from the perspective of eq. (8) is $C(|E(G)|,|V(G)|-1)$. Any idea how to determine the number of feasible combinations given by eqs. (4)-(7)?