Sobre el Problema de Matching Perfecto en Hipergrafos Bipartitos

ESCALANTE, MARIANA SILVINA; SEVERIN, DANIEL; TOLOMEI, PAOLA

Mendoza

Congreso; LXVIII Reunión Anual de Comunicaciones Científicas UMA y SOMACHI; 2019

UMA-SOMACHI

El Problema de Matching Perfecto de Mínimo Peso en Hipergrafos Bipartitos (MP) es un problema que generaliza a su homónimo sobre grafos bipartitos y, entre otras aplicaciones, permite modelar otro problema denominado Identificación Cruzada de Catálogos Estelares (véase D. Severín, Cross-identification of stellar catalogs with multiple stars: Complexity and Resolution, Electron. Notes Discr. Math. 69 (2018), 29--36).Sea H=(X,E) un hipergrafo. Un conjunto E′⊂E es un matching de H si es un conjunto de hiperaristas disjuntas, i.e. para t1,t2∈E′ diferentes, t1∩t2=∅. H es bipartito si X puede ser particionado en conjuntos A,B y cada hiperarista t satisface |t∩A|=1. Para un hipergrafo bipartito H=(A∪B,E) y t∈E, la función πA:E→A aplicada a t, i.e. πA(t), devuelve el único elemento de t∩A y la función πB:E→P(B) se define como πB(t)≐t∩B. Llamamos K al máximo valor posible de |πB(t)|.Un conjunto E′⊂E es un matching perfecto de un hipergrafo bipartito H si E′ es un matching de H que satura A, i.e. A={πA(t):t∈E′}. Sea w∈RE un vector de costos positivos. El MP consiste en obtener un matching perfecto E′ de H tal que ∑t∈E′wt sea mínimo.Notemos que H podría no admitir un matching perfecto. De hecho preguntarse por su existencia es NP-completo, aunque existen condiciones suficientes y un algoritmo polinomial cuando una de ellas se satisface (véase C. Annamalai, Finding Perfect Matchings in Bipartite Hypergraphs, Combinatorica (2018), 1285--1307).El MP puede resolverse mediante una transformación al Problema del Conjunto Estable de Máximo Peso. Sea G el grafo que surge de dicha transformación. En este trabajo: 1) caracterizamos cómo debe ser la instancia del MP para que G sea claw-free, resultando polinomial en estos casos, 2) demostramos que el MP es polinomial si |A|=2, y 3) hallamos algunas familias de desigualdades clique del poliedro surgido de la formulación del MP en el caso en que H es completo (i.e. existen todas las hiperaristas posibles) y K=2.