Suppressing an independent family of path vertices #
Remove designated vertices and join each pair of their surviving neighbors, retaining original edges between surviving vertices. When the removed vertices are independent and have degree at most two, this contracts the intervening paths and deletes isolated vertices or leaves. It is the final contraction from the region-boundary forest to the core pieces in Monien and Preis's weighted-tree argument.
def
Algebraic.Cutwidth.Bisection.RedBlack.PathSuppression.graph
{V : Type}
(B : SimpleGraph V)
(S : Finset V)
:
SimpleGraph { v : V // v ∉ S }
Remove S and replace two-edge paths through S by edges between their endpoints.
Equations
- One or more equations did not get rendered due to their size.