Given an unweighted graph $G = (V, E)$, let the cut function on this graph be defined to be: $C:2^V \rightarrow \mathbb{Z}$ such that: $$C_G(S) = |\{(u,v) \in E : u \in S \wedge v \not\in S\}|$$

For any two vertices $i,j \in V$, let the $(i,j)$ min-cut in a graph $G$ be: $$\alpha_{i,j}(G) = \min_{S \subset V : i \in S, j \not \in S}C_G(S)$$ Now, suppose we have two unweighted graphs on the same vertex set, $G = (V,E)$ and $H = (V,E')$ such that they are identical with respect to all $(i,j)$ min-cuts: $$\forall i,j \in V, \alpha_{i,j}(G) = \alpha_{i,j}(H)$$ How much can $H$ and $G$ differ with respect to their cuts? That is, how large can the following quantity be: $$\Delta(H,G) = \max_{S \subset V} |C_G(S) - C_H(S)|$$

Note that if the graphs are allowed to be weighted (or to be multigraphs), then for any $G$, there is a tree $T$ that agrees with $G$ on all min-cuts (A Gomory-Hu tree). But I am interested in the case of unweighted graphs...

  • $\begingroup$ I love how it's "function of a graph" instead of "graph of a function" $\endgroup$ – David Corwin Aug 24 '10 at 21:52

If G and H are graphs with n vertices, Δ(G,H) can be Θ(n2).

Here is an example which shows this. Let n=4k+1 be a prime. Define two graphs G=(V,E) and H=(V,E′) by V={0,1,2,…,4k}, E = {{i,j} | 1 ≤ ((j−i) mod n) ≤ k}, E′ = {{i,j} | k+1 ≤ ((j−i) mod n) ≤ 2k}. Note that G and H are both unions of k edge-disjoint Hamiltonian circuits, which implies that αi,j(G)=αi,j(H)=2k for any distinct i and j. Let S={0,1,2,…,2k−1}. Then Δ(G,H) ≥ CH(S)−CG(S) = k(3k+1)−k(k+1) = 2k2 = Θ(n2).

There is no reason to believe that this is the maximum of Δ(G,H) for given n, but it is obviously optimal up to a constant factor.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.