A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be easily shown to be imperfect yet the mathematical programming implementation of several supposedly np-hard problems return optimal solutions in near instant time for problems with very large size (millions of nodes, millions of edges). Does there exist some explanation in terms of graph decomposition to explain this?

Tarjan in his paper "decomposition by clique separators", various methodologies in using clique separators for combinatorial optimization problems. This is done using the divide and conquer paradigm. Clique separator decomposition seems to allow easy calculation of conventionally hard problems for certain graph classes which yield a clique separation tree with atoms of basic structure. Another decomposition, the tree decomposition where we map a graph to a tree that follows a set of 3 properties, is one for which certain NP-hard optimization problems become more easily solvable (in the complexity sense) and basically linear time for a bounded width on the bags of the decomposition tree.

The class of graphs for which I am working with do not yield clique separators nor do they seem to have an easy tree representation. I wanted to ask if there existed some methodology (in terms of decomposition maybe?) to explain the behaviour that I have encountered in the same vein of those above. For graphs that possess some other type of special structure to those previously mentioned. For context, I am neither a graph theorist or computer scientist so have very little competence in this stuff, I am actually an engineer working on a complex design problem which can, in a sense, be reduced down to maximum independent set on the class of graphs explained below:

The most I have been able to achieve is that if we let $G = (V,E)$ be a graph of the class, there always exists a partition with a star cut-set/separator which lets call $S$ whose deletion $G/S$ results in 2 disconnected sub-components $A$ and $B$ where $A$ is a clique and $B$ $U$ $S$ is either connected and possesses a star separator or is a clique. Basically, the graphs can always be represented in a way by a binary decomposition tree where the leaf atoms/nodes are all cliques and the articulation vertices are star separators. $K$ is a clique

enter image description here

New contributor
Student is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $\begingroup$ Hi and welcome on tcs. Your question seems interesting and on topic to me but I think that as it stands, we cannot really answer it as we miss many crucial things here: what is exactly the problem you are trying to solve? what algorithm are you currently using (you may have interesting structure in your graph without your algorithm exploiting it)? Are all your graphs in your class decomposable as in your figure? In your figure, what is $s_i$ (a vertex or a set of vertices, what are their structure?)? $\endgroup$ – holf Jan 11 at 13:48
  • $\begingroup$ The problem is maximum weight independent set on the intersection graph of 3 dimensional objects in space that form a regularised pattern. The problem is being solved as a mixed integer linear program using a highly efficient branch and cut algorithm. The only exploitation of graph structure within the integer program is the fact that its extremely easy to generate all maximum/maximal cliques of the graph which dominate all the required adjacency constraints. The graphs in the class will all be completely decomposable as in the figure. $S_i$ refers to the ith star cut set in a decomposition $\endgroup$ – Student Jan 11 at 14:38

Your Answer

Student is a new contributor. Be nice, and check out our Code of Conduct.

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.