search

TheoryInPractice / CONCUSS

Combatting Network Complexity Using Structural Sparsity
Other
8 stars 5 forks source link

Compute a lower bound on treedepth #1

Open sgsmob opened 9 years ago

sgsmob commented 9 years ago

In the count combiner classes, we can speed up computation by deciding the minimum size of a color set that might contain the motif. The tight lower bound is the treedepth of the motif. This is NP-hard to compute and even the parameterized version uses some "medium machinery" like tree decompositions that are expensive and complicated to implement. It would be nice to get some lower bound on the treedepth that is relatively easy to compute.

One easy to compute lower bound is the degeneracy. The function treedepth in lib.graph.treedepth should return this lower bound. It also is only being called in the inclusion-exclusion combiner; the other combiners should make use of them too.

bdsullivan commented 9 years ago

The degeneracy lower bound has been implemented in d78192c2e99c6555c90da85a9870701657f5b24c and is being used correctly in inclusion-exclusion. Does not appear to be applicable to other combiners without adaptation.