Skip to Main content Skip to Navigation
Conference papers

Reconstructing Set Partitions

Vladimir Grebinski 1 Gregory Kucherov 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the following combinatorial search problem: Reconstruct an unknown partition of the set [n]={1,...,n} into at most K disjoint non-empty subsets (classes) by making queries about subsets $Q_i \subseteq [n]$ such that the query returns the number of classes represented in $Q_i$. The goal is to reconstruct the whole partition with as few queries as possible. We also consider a variant of the problem where a representative of each class should be found without necessarily reconstructing the whole partition. Besides its theoretical interest, the problem has practical applications. Paper \cite{SBAW-RECOMB97} considers a physical mapping method based on hybridizing probes to chromosomes using the FISH technology. Under some reasonable assumptions, the method amounts to finding a partition of probes determined by the chromosome they hybridize to, and actually corresponds to the above formalization.
Document type :
Conference papers
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:32:28 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Wednesday, March 29, 2017 - 12:41:52 PM


  • HAL Id : inria-00098744, version 1



Vladimir Grebinski, Gregory Kucherov. Reconstructing Set Partitions. Tenth Annual ACM-SIAM Symposium on Discrete Algorithms - SODA'99, 1999, Baltimore, Maryland/US, pp.2. ⟨inria-00098744⟩



Record views


Files downloads