On the enumeration of minimal transversals

in hypergraphs

(a.k.a. minimal dominating sets in graphs)

2014/10/28 Tuesday 4PM-5PM

Room 1409

A hypergraph on V is a collection E of a subsets of a ground set V. A transversal in a hypergraph H=(V,E) is a subset T of V that intersects every set in E. We are interested in an output-polynomial algorithm for listing the set (inclusion wise) minimal transversals in a given hypergraph (known as Hypergraph Dualization or Transversal Problem). An enumeration algorithm for a set C is an algorithm that lists the elements of C without repetitions; it is said output-polynomial if it can enumerate the set C in time polynomial in the size of C and the input. The Transversal problem is a fifty-year open problem and until now not so many tractable cases are known and has deep connections with several areas of computer science: dualization of monotone functions, data mining, artificial intelligence, etc.

In this talk I will review some known results. In particular I will show that the Transversal problem is polynomially reduced to the enumeration of minimal dominating sets in co-bipartite graphs. A dominating set in a graph is a subset of vertices that intersect the closed neighborhood of every vertex. This interesting connection, we hope, will help in solving the Transversal problem by bringing structural graph theory into this area. I will also review new graph classes where we obtain polynomial delay algorithm for listing the minimal dominating sets. The talk will emphasize on the known techniques rather than a listing of known tractable cases.

Tags: MamadouMoustaphaKanté

This entry was posted on Thursday, October 16th, 2014 at 6:18 pm and is filed under 2014, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.