Efficient algorithms for dualizing large-scale hypergraphs¶
Autores: Keisuke Murakami; Takeaki Uno
Publicación: Discrete Applied Mathematics, 170, 83–94, 2014
Familia: Minimal hitting sets
Clave BibTeX: murakami2014
Resumen de los autores¶
Pendiente: se copia literal del PDF.
Qué leímos y para qué¶
Leída la versión final (DAM) y arXiv 1102.3813v2. La numeración de secciones cambia: en DAM la elección de la hiperarista mínima es §3.5 y la poda es §3.6.
Nuestro resumen¶
MMCS (Minimal-to-Maximal Conversion Search) enumera los minimal hitting sets de un hipergrafo con una búsqueda en profundidad. En cada nodo mantiene tres estructuras: el conjunto elegido \(S\), las aristas aún no cubiertas uncov(S) y, para cada vértice de \(S\), sus aristas críticas crit(v, S). Elige la arista no cubierta con menos vértices candidatos (§3.5 de DAM) y ramifica solo por esos vértices. Al probar el i-ésimo, saca de las candidatas a los i−1 anteriores, así no repite conjuntos. Descarta un hijo cuando algún vértice de \(S\) se queda sin arista crítica. Todo se actualiza de forma incremental.
RS (reverse search) recorre los mismos objetos con otro orden: procesa las aristas en orden fijo y exige que cada conjunto sea minimal respecto a un prefijo de aristas.
Para el proyecto: es la baseline principal. Nuestro mhs.Mmcs está escrito desde el artículo, no desde el código SHD de Uno, que visita entre 1,5 y 4 veces menos nodos por su reducción de datos. La sección 3.6 limita la poda a los candidatos de ramificación: es la «poda perezosa» (P7 en Propiedades de poda).