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 notin 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...
No comments:
Post a Comment