Computer Science

Colloquium Details

Set systems and their representatives: Algorithms, complexity and applications

Abstract

Other conditions one may impose on the representatives follow from equipping the elements with a distance function, i.e., viewing the base sets as subsets of a metric space, and requiring that the representatives are sufficiently spaced apart. We show that many of such generalizations lead to difficult (NP-hard) problems, even in very restricted situations, and we derive several hardness results for various combinatorial problems. Among them special instances of the map labelling problem or distance constrained labelling of graphs motivated by the frequency assignment problem. This part of the talk is based on joint work with J. Fiala (Prague) and A. Proskurowski (Eugene).

Given a family of sets, a system of their representatives is a system of elements chosen one per set. Under additional conditions even the question of existence of such a system becomes quite nontrivial. The best known and most studied are systems of distinct representatives, where we require that different sets are represented by distinct elements. An elegant characterization theorem of Hall is known, as well as polynomial time decision algorithm (via network flow or bipartite matching techniques). The Hall theorem itself has many interesting and somewhat unexpected theoretical consequences (ranging from Latin squares over graph labellings to Hamiltonian cycles in planar triangulations). We will show some of them.

Biography

Jan Kratochvil's home page is at http://kam.mff.cuni.cz/~honza/