Plan del artículo: framework validado y comparación con MMCS y RS¶
Fecha: 2026-11-17. Decisión de Vladimir: los errores del código original se publican como parte del artículo. El objetivo es que quien use esos algoritmos hoy tenga implementaciones en las que pueda confiar.
Tesis del artículo¶
Reescrita el 2026-11-17, después de la revisión bibliográfica y de las mediciones con RUNC-M (docs/revision-bibliografica-br-pivot.md, sección 6). Sustituye a la versión anterior, según la cual "MMCS y RS superan a todos". Eso ya no es cierto: RUNC-M les gana en matrices densas o con pocas filas.
Hasta donde encontramos, los algoritmos latinoamericanos de testores típicos (fast-BR, fast-CT_EXT, GCreduct) no se habían comparado con los de minimal hitting sets, aunque calculan lo mismo. Las otras dos familias que resuelven el problema son la de Murakami y Uno (MMCS, RS) y la escuela rusa de Djukova (RUNC-M). Las comparamos en un framework común, validado por conjunto de reductos. En las matrices probadas, los algoritmos latinoamericanos quedan detrás de las otras dos familias; en la primera comparación, fast-BR tarda entre 1,4 y 12 veces lo que MMCS, o agota el límite (pendiente de las corridas completas). Una ablación dentro de fast-BR muestra la causa principal: fast-BR elige la fila pivote solo en la raíz. Si la elige en cada nodo, se convierte en RUNC-M y queda entre 0,9 y 3,3 veces el tiempo del RUNC-M original en C++. Entre las dos familias rápidas no hay una que gane siempre. El filtrado de toda la lista de candidatos (RUNC-M) gana con densidad alta o con pocas filas. La poda perezosa (MMCS) gana en matrices ralas con muchas filas. Además, el framework destapó errores de conteo en implementaciones publicadas; quedan corregidos, con pruebas de regresión.
Lo que no se reclama: br-pivot no es un algoritmo nuevo, es RUNC-M (Djukova y Prokofjev 2015) reconstruido desde fast-BR. Tampoco es nueva la comparación de RUNC-M con MMCS y RS: está en la tesis de Prokofjev (2016). Nuestro aporte en ese punto es repetirla con un MMCS más rápido que el de SHD, y con eso el cruce se mueve.
Título de trabajo: Three families, one problem: testor, Djukova-school and minimal hitting set algorithms compared in a validated framework.
Aportes¶
- Framework. Trece programas con un contrato común: entra una matriz básica, sale JSON con conteo, candidatos, tiempo y conjunto de reductos. La validación es por conjunto y la referencia es independiente.
- Auditoría de corrección. Cinco errores en código publicado, con la condición que dispara cada uno, su efecto en los paquetes públicos (pequeño: tres matrices) y pruebas de regresión.
- Comparación entre las tres familias. Algoritmos latinoamericanos, RUNC-M, MMCS y RS, en todos los reductos y en los más cortos.
- Ablación. Cuando fast-BR elige la fila pivote en cada nodo se convierte en RUNC-M. Ese es el ingrediente que explica la mayor parte de la diferencia.
- Cuándo gana cada estrategia. Un barrido controlado de densidad, filas y columnas, que da el cruce entre el filtrado de toda la lista y la poda perezosa. Sirve para elegir algoritmo según la matriz, y conecta con la idea de meta-algoritmo de la tesis de 2022.
- Secundario: sensibilidad al orden de filas y columnas.
Debilidades conocidas: - El cruce se midió en matrices aleatorias, y dermatology no lo sigue. - Todo corrió en una máquina de 2 núcleos. - RUNC-M no se puede redistribuir sin permiso de sus autores.
Inventario de algoritmos¶
| Algoritmo | Problema | Original | En el framework | Validado por conjunto (442 pequeñas y 8 UCI) |
|---|---|---|---|---|
| GCreduct | todos | Java | copia corregida | sí |
| fast-BR | todos | Java | copia corregida | sí |
| fast-CT_EXT | todos | Java | copia corregida | sí |
| MMCS | todos | C (SHD de Uno) | Java nuevo, y SHD como externo | sí, los dos |
| fast-BR con pivote (ablación) | todos | no existe | mhs.Br (modos root, bound, pivot) |
sí, 300 aleatorias y pruebas de regresión |
| RS | todos | C (SHD de Uno) | Java nuevo, y SHD como externo | sí, los dos |
| RUNC-M (Djukova y Prokofjev) | todos | C++ (Nikiforov, sin licencia) | externo, scripts/fetch_runcm.sh, runcm en el runner |
sí, 453 matrices pequeñas |
| MinReduct | más cortos | Java | copia corregida | sí |
| sRGA | más cortos | Java | copia corregida y Srga nuevo |
Srga sí; la copia corregida solo por conteo |
| CAMARDF | más cortos | C++ | Camardf en Java |
sí |
| MMCS acotado | más cortos | no existe | mhs.Mmcs -shortest |
sí |
En las 8 UCI, lung-cancer quedó sin GCreduct ni fast-CT_EXT por el límite de 60 s.
Dentro de la primera versión, desde el 2026-11-20: RegularSearch y YYC de Lefebre (github.com/J41R0/RegularSearch, MIT; en el runner regsearch y yyc, ver scripts/fetch_regsearch.sh). Fuera de la primera versión: HTC-BDD (Toda), RoPM y MiLIT. De este último se puede correr el JAR, pero no redistribuirlo sin permiso. FastRS (Lefebre, sin publicar), MHS2 y el banco ampliado (HTC-BDD, datasets de Uno) quedan para un posible trabajo conjunto con Jairo Lefebre, decidido el 2026-11-20 (opción c en docs/regularsearch-y-jairo.md §3.2).
Hecho a la fecha¶
- Verificación: 442 matrices pequeñas y 13 de UCI. Validación por conjunto de los 12 programas en las 442 y en 8 UCI.
- Errores documentados en
docs/hallazgos-errores.md; pruebas entests/(11 matrices, por conteo y por conjunto). - Auditoría de los paquetes publicados (
experiments/audit/). - Piloto de ordenamiento (
experiments/ordering/). - Primera comparación (
experiments/baseline/) y ablación (docs/mmcs-y-propuesta-articulo.md).
Falta¶
- ~~Ablación que cierra el argumento: fast-BR con fila pivote dinámica.~~ Hecho el 2026-11-17:
mhs.Br -mode pivotqueda a menos de 2.6 veces del tiempo de MMCS, desde agotar el límite o 10 veces más (docs/mmcs-y-propuesta-articulo.md, sección "fast-BR con fila pivote en cada nodo"). - Corridas completas en una máquina con más núcleos: las 663 sintéticas distintas y las UCI, con límites de horas.
- Reductos más cortos: comparación sistemática de MinReduct,
Srga,Camardfy MMCS acotado. - Revisión bibliográfica: primera pasada hecha el 2026-11-17 (
docs/revision-bibliografica-br-pivot.md).br-pivotes en esencia RUNC-M (Djukova y Prokofjev, 2015): no se presenta como algoritmo nuevo y hay que citar RUNC-M y OPT. La tesis de Prokofjev (2016) ya compara RUNC-M y OPT contra MMCS y RS; no se encontró comparación de BR, fast-BR, CT_EXT, YYC o GCreduct contra MMCS o RS. Falta leer el artículo original de RUNC-M y confirmarlo con los asesores (pregunta 5). El código de RUNC-M se recuperó de Software Heritage, quedó validado y entra como baseline. En la primera medición gana en matrices densas y pierde contra MMCS en las ralas (sección 6 de la revisión). Los artículos que faltan están endocs/articulos-por-conseguir.md. 4b. Explicar dermatology: sale del cruce del barrido. Probar matrices con columnas correlacionadas o filas de peso desigual. 4c. Hecho el 2026-11-19 (parcial):github.com/ppprok/dual(MIT, commit 224ebf9) se compila sin cmake conscripts/fetch_ppdual.sh(driver propioscripts/ppdual_main.cpp) y entra al runner comoppdual(RUNC-M) yppdual-runc(fila 1). Validación por conjunto de reductos contra la referencia de Python en 453 matrices (experiments/baseline/ppdual_vs_runcm.py): coincidenppdual,ppdual-runcyruncmen las 453. Nodos de búsqueda: 117879 contra 117060 (ppdualcuenta distinto; no se comparan como misma métrica). Tiempos (20 matrices, mediana de 3,results/ppdual_vs_runcm_time.md):ppduales 2 a 5 veces más rápido queruncmde Nikiforov en las 12 sintéticas de 2000x30 y le gana ashd-mmcsen todas, incluidas las ralas (ej. densidad 0,17: 347 ms contra 1853 deruncmy 975 deshd-mmcs; antesmmcsen Java tardaba 737).runcmgana solo en dermatology y lung-cancer. Consecuencia: la afirmación «MMCS gana en ralas con muchas filas» no se sostiene contra la implementación de Prokofyev; era en parte efecto de la implementación de Nikiforov. Hay que rehacer el barrido (runcm_sweep.py) conppdualy reescribir esa parte del artículo. Pendiente: causa (la ruta de ancho fijo de 32/64/128 columnas es hipótesis, no medida), medirppdual-runccontrappdualpor nodos y tiempo para separar fila mínima de filtrado, y correr sobresynth.py.runcmde Nikiforov queda solo como comparación. 4d. Verificación del sesgo y candidatos (2026-11-19). (a) El driverppdualno sesga: leer la matriz y arrancar cuesta 2 ms, mismas banderas-O3queruncm, salida a/dev/nullen ambos. (b) Candidatos evaluados de nuestros programas Java (experiments/baseline/candidates.py,results/candidates.md):mmcsevalúa menos quebr-pivoten 17 de 20 matrices (br-pivot/mmcs entre 0,94 y 2,76 en las sintéticas; en lung-cancer es 0,63) y quersen todas (1,0 a 10).brsin pivote agota 60 s o evalúa de 1 a 1,5 millones de veces más en matrices ralas pequeñas. Es decir: por candidatos MMCS gana casi siempre, y por tiempoppdualle gana en ralas. El contador de cada programa externo tiene otra unidad (iteraciones de SHD, nodos deruncm/ppdual), así que no entra. La diferencia de tiempo a igualdad de trabajo es costo por candidato de la implementación, no del algoritmo. Esto no se puede cerrar con programas heterogéneos: hace falta el framework de abajo. 4e. Framework Java de primitivas equivalentes (pedido por Vladimir). Un solo núcleo con la misma representación (bitsets), el mismo lector y los mismos contadores, donde MMCS, RUNC-M, br-pivot y RS son combinaciones de políticas intercambiables: elección de fila (primera, mínimos candidatos), filtrado de candidatos (ninguno, lista completa por nodo, perezoso), mantenimiento de filas críticas, orden de columnas. Cada primitiva cuenta sus ejecuciones (extensiones probadas, actualizaciones de crit, palabras tocadas). Así, tiempo y candidatos se comparan con todo lo demás igual, y los programas externos (SHD, ppdual) quedan como referencia de corrección y de cota, no como base de la tesis. Diseño por acordar antes de escribir código. Decidido el 2026-11-19: el núcleo convive conmhs.Mmcs,RsyBry se valida contra ellos por conjunto de reductos. 4e-bis. Núcleo escrito (2026-11-19):java/src/mhs/core/(Core,Rep,BitsetRep,ListRep,Matrix;build.shlo compila). Un motor y tres ejes:-rep bitset|list,-row min|first,-cand lazy|filter; ocho configuraciones en el runner comocore-<rep>-<row>-<cand>. Identidades que declara:bitset-min-lazy=mhs.Mmcs;bitset-first-lazy=Mmcs -firstrow;*-min-filter= RUNC-M;*-first-filter= RUNC. Verificado (experiments/baseline/core_validate.py,results/core_validate.md): las 8 configuraciones coinciden por conjunto de reductos con la referencia de Python en 453 matrices, y las dos identidades lazy coinciden conmhs.Mmcsen Nodes y Candidates en las 453. Las identidades con RUNC-M y RUNC no están verificadas (solo por conjunto): falta comparar nodos conppdualyppdual-runc, que cuentan distinto. Contadores iguales en todas: Nodes, Extends, Filters, Candidates = Extends + Filters, RowScans, Work (palabras o elementos). Fuera de la v1: RS (orden fijo de filas con prefijo) yBr. Comparación completa enexperiments/baseline/core_compare.py(en curso al escribir esto). Resultados completos (20 matrices, mediana de 3, límite 30 s;results/core_compare.md). Corrección: un dato parcial que escribí antes («list10 a 25 veces más lento quebitset») era un error de lectura de columnas: esos 19 s eranbitset-first-lazy. Lo correcto: (1) Con la misma representación, lazy gana a filter en tiempo en las 20 matrices conbitset-min(ej. 744 contra 1730 ms; student-mat 1836 contra 5540). Filter hace 3 a 4 veces más pruebas de extensión (785 mil contra 2,84 millones) a cambio de solo 5 % menos nodos (556100 contra 524946). (2) Fila mínima contra primera fila:firstse dispara en matrices ralas (19258 ms contra 744; con filter agota 30 s) y se acerca aminal subir la densidad; en la más densa (0,80)first-lazyes más rápido quemin-lazy(52 contra 97 ms). (3) Representación:listhace de 3 a 6 veces menos operaciones elementales quebitset(unidad distinta: elementos contra palabras), pero el tiempo es parecido o algo peor (867 contra 744 ms en la más rala); gana en pocas matrices (student-mat 1070 contra 1836 ms; dermatology 103 contra 116). Con 2000 filas y densidad ≥ 0,17, las listas no ganan de forma clara. (4) Consecuencia parappdual: en este motor,min-filter(la estrategia de RUNC-M) no es más rápida quemin-lazy(MMCS), y sus nodos (524946) son cercanos a los deppdual(541149) yruncm(544566) en la primera matriz: parecido, no idéntico. Entonces la ventaja de 2 a 5 veces deppdualsobremhs.Mmcsno sale de la estrategia sino del costo por candidato de la implementación (C++, estructuras). Es una inferencia: falta construir una configuración Java que reproduzca ese costo, o instrumentarppdual. Y no sé cuánto aporta C++ frente a JVM. No hay base para la frase «MMCS gana en ralas» ni para «RUNC-M gana en ralas»; sí para: a igualdad de implementación, lazy gana a filter y fila mínima gana a primera fila en ralas. Zona muy rala (2026-11-20,experiments/baseline/core_sparse.py,results/core_sparse.md): 14 matrices de densidad real 2,7 a 5,2 % (913×60 a 4000×100, 2 semillas, mediana de 3, límite 40 s).list-min-lazygana abitset-min-lazyen 13 de 14, hasta 2,2 veces (4000×100, 0,029: 6542 contra 14198 ms);list-min-filtergana abitset-min-filteren las 14. Confirma la hipótesis de Vladimir (4f(e)) en ese rango. Falta el cruce entre 5 y 17 % y matrices de cientos de columnas, donde la cantidad de reductos explota. 4f. Comentarios de Lazo (2026-11-19) y decisiones que implican. (a) Construcción de la matriz básica: unos algoritmos parten de la tabla de decisión y otros de la matriz básica; Lazo pide contar el tiempo de construirla, Vladimir prefiere tratarla aparte. Propuesta: reportar siempre tres cifras,t_construcción,t_búsqueday su suma, y un algoritmo que no construye la matriz (RegularSearch, CAMARDF desde la tabla) entra con su tiempo total. Lazo envió un artículo con Memo (autómata para la matriz básica, sección To Appear de la revista): pendiente recibirlo y leerlo. (b) Densidad de unos como variable de referencia: Lazo y Saúl Solorio lo empezaron y no lo terminaron; coincide con nuestro cruce y con dermatology (4b). No decir «la densidad predice el ganador» sin probar que filas, columnas y distribución de pesos no lo explican mejor. (c) Lazo trabaja con colegas de Namibia en cotas de teoría de hipergrafos para MiLIT y MinReduct (más cortos); preguntar por el artículo. (d) Lista de «cosas que hacen los algoritmos» de Lazo (core, orden, fila pivote): pedirla; es casi el mismo eje de políticas del framework. (e) Hipótesis de Vladimir: los algoritmos que guardan el discernimiento en listas enlazadas son muy eficientes en matrices ralas por el bajo costo por candidato. Contrastar en el framework con la representación como un eje más (bitset contra listas de adyacencia), sin tocar la estrategia. - Licencias: pedir permiso a Nikiforov, Djukova o Prokofjev para RUNC-M. Pedir permiso para
Camardf.javaa los autores de CAMARDF, o declararlo reimplementado desde el artículo y comprobar que lo es. - Repositorio público para el artículo: separar lo que se puede publicar (código propio, correcciones, código nuevo) de lo que no (
legacy/, SHD, MiLIT). - Redacción.
Calendario hacia IJCRS 2027 (fecha límite: 15 de diciembre de 2026)¶
| Semana | Trabajo |
|---|---|
| 17 a 23 nov | Congelar el alcance. Ablación de fast-BR con pivote. Correo a los autores de CAMARDF. Conseguir la máquina. |
| 24 a 30 nov | Corridas completas. Comparación de reductos más cortos. |
| 1 a 7 dic | Borrador completo. |
| 8 a 15 dic | Revisión de los asesores y envío. |
Si la máquina o la revisión de los asesores se retrasan, MCPR 2027 (fecha probable: enero o febrero, sin confirmar) es la alternativa.
Decisiones pendientes¶
- IJCRS o MCPR.
- Qué máquina usar para las corridas largas.
- Si MiLIT entra en la comparación (corriendo el JAR, sin redistribuirlo).
- ~~Cuándo se les cuenta a los asesores.~~ Hecho el 2026-11-17: la página de ideas tiene una sección con los errores, RUNC-M y la nueva tesis.