Enumerating Maximal Chain Subgraphs Sample Clauses

Enumerating Maximal Chain Subgraphs. The problem of enumerating in bipartite graphs all subgraphs with certain properties has already been considered in the literature. These concern for instance maximal bicliques for which polynomial delay enumeration algorithms in bipartite [24, 57] as well as in general graphs [23, 57] were provided. In the case of maximal induced chain subgraphs, their enumeration can be done in total polynomial time as it can be reduced to the enumeration of a particular case of the minimal hitting set problem [30] (where the sets in the family are of cardinality 4). However, the existence of a polynomial delay algorithm for this problem remains open. Regarding the problem of enumerating maximal edge induced chain subgraphs in bipar- tite graphs, in [34] the authors deal with it in the form of enumerating minimal interval order extensions of interval orders (see Section 1.6 for the relation between these two problems). We improve this result by proposing a polynomial space and polynomial delay algo- rithm to enumerate all maximal chain subgraphs of a bipartite graph. We also provide an analysis of the time complexity of this algorithm in terms of input size. In order to do this, we prove some upper bounds on the maximum number of maximal chain subgraphs of a bipartite graph. This is also of intrinsic interest as combinatorial bounds on the max- imum number of specific subgraphs in a graph are difficult to obtain and have received a lot of attention (see for e.g. [38, 64]). We start by proving the following result: