Russian Doll Search for Computing Maximum Vertex Weight Hereditary Structures in Graphs

Copyright Eugene Lykhovyd, 2017-2018.
Copyright Mykyta Makovenko, 2018.

See LICENSE for more details.

A graph property is hereditary on induced subgraphs if it holds for all vertex-induced subgraphs of
a graph satisfying this property. Given a fixed nontrivial, hereditary graph property and a
vertex-weighted graph, we consider the problem of finding the maximum weight subset of vertices
inducing a subgraph satisfying this property. Russian Doll Search provides an attractive framework
for solving this class of problems. We develop a C++ implementation of this approach, which can be
used to find maximum vertex weight structures for any hereditary property, as long as one can
provide an efficient feasibility verification procedure for a subgraph obtained from a feasible
subgraph by adding a new vertex.

See https://wp.lykhovyd.com/rds/ for more details.