Efficiently Listing Combinatorial Patterns in Graphs

The main contribution of this work is the presentation of optimal algorithms for four different problems of listing patterns in graphs. These algorithms are framed within the same generic approach, based in a recursive partition of the search space that divides the problem into subproblems. The key to an efficient implementation of this approach is to avoid recursing into subproblems that do not list any patterns. With this goal in sight, a dynamic data structure, called the certificate, is introduced and maintained throughout the recursion. Moreover, properties of the recursion tree and lower bounds on the number of patterns are used to amortize the cost of the algorithm on the size of the output. The first problem introduced is the listing of all k-subtrees: trees of fixed size k that are subgraphs of an undirected input graph. The solution is presented incrementally to illustrate the generic approach until an optimal output-sensitive algorithm is reached. This algorithm is optimal in the sense that it takes time proportional to the time necessarily required to read the input and write the output. The second problem is that of listing k-subgraphs: connected induced subgraphs of size k in an undirected input graph. An optimal algorithm is presented, taking time proportional to the size of the input graph plus the edges in the k-subgraphs. The third and fourth problems are the listing of cycles and listing of paths between two vertices in an undirected input graph. An optimality-preserving reduction from listing cycles to listing paths is presented. Both problems are solved optimally, in time proportional to the size of the input plus the size of the output. The algorithms presented improve previously known solutions and achieve optimal time bounds.