Expand description
Kernelize match-compatibility graphs to improve top-down search efficiency.
The problem of computing the minimum assembly index of a molecule can be reduced to finding the maximum weight clique in a compatibility graph over matches (i.e., pairs of non-overlapping isomorphic subgraphs). Strucutral properties of this graph can be used to determine match pairs (i.e., nodes) that definitely will or definitely won’t be used in an optimal solution. We call the process of identifying these nodes kernelization. Uses the strategies of neighborhood removal, isolated vertex removal, and domination as described in Section 5.2 of Lamm et al. (2019). (Note that they solve the equivalent problem of weighted independent set.)
Enums§
- Kernel
Mode - Graph kernelization strategy when searching using the clique reduction.