Enumerating objects of a specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. The optimization problem Tropical Connected Set is strongly related to the Graph Motif problem which deals with vertex-colored graphs and has various applications in metabolic networks and biology. A tropical connected set of a vertex-colored graph is a subset of the vertices which induces a connected subgraph in which all colors of the input graph appear at least once; among others this generalizes steiner trees. We investigate the enumeration of the inclusion-minimal tropical connected sets of a given vertex-colored graph. We present algorithms to enumerate all minimal tropical connected sets on colored graphs of the following graph classes: on split graphs in running in time O~*(1.6402~n), on interval graphs in O~*(1.8613~n) time, on cobipartite graphs and block graphs in O~*(3~(n/3)). Our algorithms imply corresponding upper bounds on the number of minimal tropical connected sets in graphs on n vertices for each of these graph classes. We also provide various new lower bound constructions thereby obtaining matching lower bounds for cobipartite and block graphs.
展开▼
