Suppose a graph, $G = (V,E)$ is characterized as a lattice/network of cliques as in the picture below. Does there exist some decomposition principle (i.e. on the right) for $G$, that yields some special structure that may be used to explain efficiencies experienced with what are supposed to be combinatorial hard problems?

enter image description here

  • $\begingroup$ Did you check the condition that each graph vertex appears in a connected subtree of bags of the decomposition? $\endgroup$ – David Eppstein Jan 7 at 6:35
  • $\begingroup$ Sorry I must've overlooked that property. A more proper question would be, does there exist a decomposition technique where the type of described graph yields some structure similar to what is displayed here: imgur.com/a/lGQrVH3 $\endgroup$ – Student Jan 7 at 6:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.