Generalized Cuts and Spanning Subgraphs

Student: Yuki Saka
Advisor: Leonid Khachiyan, Department of Computer Science


My name is Yuki Saka, a senior at University of California, Berkeley. I study computer science and mathematics. Here is my other homepage. This summer I am working with my advisor, Professor Leonid Khachiyan. We study combinatorial properties and enumeration algorithm of generalized cuts and spanning subgraphs.

Project Description

Suppose we are given a discrete set V = {1,..,n} and a family of subsets of V, F = {V1 ... Vk} such that the union of all elements in F covers V. We are interested in the following combinatorial objects: B = {minimal subfamily of F whose union covers V} and A = {maximal subfamily of F whose union does not cover V}. If our family consists of elements each of which has exactly two elements, then the pair (V,F) is a graph, A is a set of spanning trees, and B is a set of complements to cuts. In this particular case, we have an inequality: |A| <= (|V|-1)|B|. We can also generate these families efficiently in this special case [1], [2].

There is also an inequality in the general case proved in [3]:
|A| <= (|B||F|)log|V|

It is also known that the generation of A is NP-hard, but the generation of B can be done in quasi-polynomial time. The question we pursue is this: Can we improve the inequality in the general case? Can we obtain a polynomial-time algorithm for the generation of B?

Special case: spanning trees and cuts

Inequality

If T is a set of spanning trees and C a set of complements to cuts, then the inequality |C| <= (|V|-1)|T| can be established by looking

Generation Problem

There is an efficient algorithm for the generation of all spanning trees of a given graph. We must be a bit careful when talking about efficiency in this case however, because the number of spanning trees maybe exponential in |V| or |E|. Hence we have no hope of generating the set of spanning trees in time polynomial in |V| or |E|. Instead, we consider the time per spanning tree generated.

References

[1] R.C. Read and R.E. Tarjan, Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks, 5, 1975, 357-372.
[2] J.S. Provan and D.R. Shier, A paradigm for listing (s,t)-cuts in digraphs, algorithmica 15 (4), 1996, 351-372.
[3] E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan, An inequality for polymatroid functions and its applications. DIMACS Technical Report 2001-14.