Is there a tractable way to define an approximate distribution over small vertex separators of the graph? I'm looking for something along the lines of [Bayati,2008], a way to turn a single "this is a separator" constraint into a product of several constraints that are easier to enforce. Small true separators may be impossible, in which case approximate separators would do (any cycle that goes through approximate separator must have length >k).

Motivation is constructing a message-passing scheme without short feedback loops.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.