The intersection of subgroups in free groups and linear programming

We study the intersection of finitely generated subgroups of free groups by utilizing the method of linear programming. We prove that if H₁ is a finitely generated subgroup of a free group F, then the WN-coefficient σ(H₁) of H₁ is rational and can be computed in deterministic exponential time in the size of H₁. This coefficient σ(H₁) is the minimal nonnegative real number such that, for every finitely generated subgroup H₂ of F, it is true that r ¯ (H₁, H₂) ≤ σ(H₁) r ¯ (H₁) r ¯ (H₂) , where r ¯ (H) : = max (r (H) - 1 , 0) is the reduced rank of H, r (H) is the rank of H, and r ¯ (H₁, H₂) is the reduced rank of the generalized intersection of H₁ and H₂. We also show the existence of a subgroup H2∗=H2∗(H1) of F such that r¯(H1,H2∗)=σ(H1)r¯(H1)r¯(H2∗), the Stallings graph Γ(H2∗) of H2∗ has at most doubly exponential size in the size of H₁ and Γ(H2∗) can be constructed in exponential time in the size of H₁.