Particionamiento de matroides

Subdivisión en unos pocos conjuntos independientes

La partición de matroides es un problema que surge en el estudio matemático de los matroides y en el diseño y análisis de algoritmos . Su objetivo es particionar los elementos de un matroide en la menor cantidad posible de conjuntos independientes. Un ejemplo es el problema de calcular la arboricidad de un grafo no dirigido , el número mínimo de bosques necesarios para cubrir todos sus bordes. La partición de matroides se puede resolver en tiempo polinomial , dado un oráculo de independencia para el matroide. Se puede generalizar para mostrar que una suma de matroides es en sí misma un matroide, para proporcionar un algoritmo para calcular rangos y conjuntos independientes en sumas de matroides, y para calcular el conjunto independiente común más grande en la intersección de dos matroides dados. ^[1]

Ejemplo

Una partición de los bordes del gráfico bipartito completo K _4,4 en tres bosques, mostrando que tiene arboricidad como máximo tres

La arboricidad de un grafo no dirigido es el número mínimo de bosques en los que se pueden dividir sus aristas o, equivalentemente (añadiendo aristas superpuestas a cada bosque según sea necesario), el número mínimo de bosques que se extienden y cuya unión es el grafo completo. Una fórmula demostrada por Crispin Nash-Williams caracteriza la arboricidad exactamente: es el máximo, sobre todos los subgrafos del grafo dado , de la cantidad . ^[2] ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle \left\lceil {\frac {|E(H)|}{|V(H)|-1}}\right\rceil }$

Los bosques de un grafo forman los conjuntos independientes del matroide gráfico asociado , y la cantidad que aparece en la fórmula de Nash-Williams es el rango del matroide gráfico de , el tamaño máximo de uno de sus conjuntos independientes. Por lo tanto, el problema de determinar la arboricidad de un grafo es exactamente el problema de partición del matroide para el matroide gráfico. El hecho de que los elementos de este matroide no se puedan dividir en menos de subconjuntos independientes es entonces simplemente una aplicación del principio del palomar que dice que, si los elementos se dividen en conjuntos de tamaño como máximo , entonces se necesitan al menos conjuntos. La dirección más difícil de la fórmula de Nash-Williams, que se puede generalizar a todos los matroides, es la prueba de que siempre existe una partición de este tamaño. ^[1] ${\displaystyle |V(H)|-1}$ ${\displaystyle H}$ ${\displaystyle |E(H)|}$ ${\displaystyle {\frac {|E(H)|}{|V(H)|-1}}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x/y}$

Fórmula para el tamaño de la partición

Para generalizar la fórmula de Nash-Williams, se puede reemplazar por un matroide , y el subgrafo de con una restricción de a un subconjunto de sus elementos. El número de aristas del subgrafo se convierte, en esta generalización, en la cardinalidad del subconjunto seleccionado, y la fórmula para el tamaño máximo de un bosque en se convierte en el rango . Por lo tanto, el número mínimo de conjuntos independientes en una partición del matroide dado debe estar dado por la fórmula ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle M|S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle H}$ ${\displaystyle |S|}$ ${\displaystyle |V(H)|-1}$ ${\displaystyle H}$ ${\displaystyle r(S)}$ ${\displaystyle M}$

${\displaystyle k(M)=\max _{S}\left\lceil {\frac {|S|}{r(S)}}\right\rceil }$.

Esta fórmula es de hecho válida, y Edmonds (1965) le dio una prueba algorítmica. ^{[1] [3]} En otras palabras, un matroide se puede dividir en, como máximo, subconjuntos independientes, si y solo si para cada subconjunto de , la cardinalidad de es como máximo . ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle k\cdot r(S)}$

Algoritmos

El primer algoritmo para la partición de matroides fue dado por Edmonds (1965). ^[3] Es un algoritmo de aumento de caminos incrementales que considera los elementos del matroide uno por uno, en un orden arbitrario, manteniendo en cada paso del algoritmo una partición óptima para los elementos que se han considerado hasta ahora. En cada paso, al considerar un elemento que aún no se ha colocado en una partición, el algoritmo construye un grafo dirigido que tiene como nodos los elementos que ya se han particionado, el nuevo elemento , y un elemento especial para cada uno de los conjuntos independientes en la partición actual. Luego forma un grafo dirigido en este conjunto de nodos, con un arco dirigido para cada elemento del matroide que se puede agregar al conjunto de particiones sin hacer que se vuelva dependiente, y con un arco dirigido para cada par de elementos del matroide de modo que al eliminarlo de su partición y reemplazarlo con se forme otro conjunto independiente. ^{[1] [3]} ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \bot _{i}}$ ${\displaystyle k}$ ${\displaystyle G_{x}}$ ${\displaystyle \bot _{i}\rightarrow y}$ ${\displaystyle y}$ ${\displaystyle i}$ ${\displaystyle z\rightarrow y}$ ${\displaystyle (y,z)}$ ${\displaystyle z}$ ${\displaystyle y}$

Ahora hay dos casos:

• Si este grafo contiene una ruta dirigida desde un elemento hasta el nuevo elemento considerado , entonces la ruta más corta de dicha ruta (o, de manera más general, cualquier ruta que no tenga aristas de atajo) describe una secuencia de cambios que se pueden realizar simultáneamente en los conjuntos de particiones para formar una nueva partición, con el mismo número de conjuntos, que también incluye . En este caso, el algoritmo realiza estos cambios y continúa. ${\displaystyle \bot _{i}}$ ${\displaystyle x}$ ${\displaystyle x}$
• Si, por otra parte, no existe tal camino, entonces sea que consiste en los elementos del matroide desde los cuales es alcanzable en . Cada conjunto en la partición actual debe ser un conjunto independiente maximal en la restricción , porque si algún elemento de pudiera agregarse al conjunto de partición en la restricción, entonces existiría un arco (si el conjunto de partición no es maximal en el matroide completo ) o un arco donde (si el conjunto de partición no es maximal en pero maximal en el matroide completo). En cualquier caso, la existencia de este arco contradice la construcción supuesta del conjunto , y la contradicción prueba que cada conjunto de partición es maximal. Por lo tanto, por la fácil dirección de la fórmula de partición del matroide, el número de conjuntos necesarios para particionar es al menos ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle D}$ ${\displaystyle M|S}$ ${\displaystyle y}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle \bot _{i}\rightarrow y}$ ${\displaystyle i}$ ${\displaystyle M}$ ${\displaystyle z\rightarrow y}$ ${\displaystyle z\notin S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

${\displaystyle \left\lceil {\frac {|S|}{r(S)}}\right\rceil =\left\lceil {\frac {kr(S)+1}{r(S)}}\right\rceil =k+1}$,

Por lo tanto, en este caso, el algoritmo puede encontrar una partición óptima colocando en su propio nuevo conjunto independiente y dejando los otros conjuntos independientes sin cambios. ^{[1] [3]} ${\displaystyle x}$

El algoritmo general, entonces, considera cada elemento del matroide dado a su vez, construye el grafo , prueba qué nodos pueden alcanzar , y usa esta información para actualizar la partición actual de modo que incluya . En cada paso, la partición de los elementos considerados hasta ahora es óptima, por lo que cuando el algoritmo termina habrá encontrado una partición óptima para todo el matroide. Probar que este algoritmo es correcto requiere demostrar que un camino sin atajos en el grafo auxiliar siempre describe una secuencia de operaciones que, cuando se realizan simultáneamente, preserva correctamente la independencia de los conjuntos en la partición; Edmonds dio una prueba de este hecho. Debido a que el algoritmo solo aumenta el número de conjuntos en la partición cuando la fórmula de partición del matroide muestra que se necesita un número mayor, la corrección de este algoritmo también muestra la corrección de la fórmula. ^{[1] [3]} ${\displaystyle x}$ ${\displaystyle G_{x}}$ ${\displaystyle x}$ ${\displaystyle x}$

Aunque este algoritmo depende únicamente de la existencia de un oráculo de independencia para su corrección, en muchos casos se pueden encontrar algoritmos más rápidos aprovechando la estructura más especializada de tipos específicos de matroides (como los matroides gráficos ) a partir de los cuales se ha definido un problema de partición particular. ^[4]

Problemas relacionados

Una suma matroide (donde cada una es una matroide) es en sí misma una matroide, teniendo como elementos la unión de los elementos de los sumandos. Un conjunto es independiente en la suma si puede ser dividido en conjuntos que son independientes dentro de cada sumando. El algoritmo de partición de matroides se generaliza al problema de probar si un conjunto es independiente en una suma matroide. Su corrección puede usarse para probar que una suma matroide es necesariamente una matroide. ^{[3] [4]} Un problema extendido, que también se llama a veces partición de matroides , es encontrar un conjunto más grande que sea independiente en la suma matroide, es decir, un conjunto más grande que pueda ser dividido en conjuntos que sean disjuntos en cada matroide de entrada. Cunningham ^[5] presenta un algoritmo para resolver este problema en matroides de O ( n ) n -elementos usando llamadas a un oráculo de independencia . ${\displaystyle \sum _{i}M_{i}}$ ${\displaystyle M_{i}}$ ${\displaystyle O(n^{2.5})}$

El problema de la intersección de matroides consiste en encontrar el conjunto más grande que sea independiente en dos matroides y . Puede resolverse convirtiéndolo en un problema de suma de matroides equivalente: si es una base de la suma , donde es el dual de , entonces debe tener rango completo en y al eliminar un conjunto independiente máximo de de se obtiene una intersección máxima. ^[6] ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle B}$ ${\displaystyle M_{1}+M_{2}^{*}}$ ${\displaystyle M_{2}^{*}}$ ${\displaystyle M_{2}}$ ${\displaystyle B}$ ${\displaystyle M_{2}^{*}}$ ${\displaystyle M_{2}^{*}}$ ${\displaystyle B}$

La partición de matroides es una forma de problema de cobertura de conjuntos , y el problema de empaquetamiento de conjuntos correspondiente (encontrar un número máximo de conjuntos que abarcan disjuntos dentro de un matroide dado) también es de interés. Puede resolverse mediante algoritmos similares a los de la partición de matroides. ^[4] Los problemas de empaquetamiento de conjuntos fraccionarios y de cobertura de conjuntos asociados con un matroide (es decir, asignar un peso a cada conjunto independiente de tal manera que para cada elemento el peso total de los conjuntos que lo contienen sea como máximo uno o al menos uno, maximizando o minimizando el peso total de todos los conjuntos, respectivamente) también pueden resolverse en tiempo polinomial utilizando métodos de partición de matroides. ^[1]

Además de su uso para calcular la arboricidad de un gráfico, la partición de matroides se puede utilizar con otros matroides para encontrar un subgráfico de un gráfico dado cuyo grado promedio sea máximo, y para encontrar la tenacidad de las aristas de un gráfico (una variante de la tenacidad de gráficos que implica la eliminación de aristas en lugar de vértices). ^[1]

La partición numérica con restricciones de matroides es un problema diferente en el que k (la cantidad de subconjuntos en la partición) es fija. Hay k matroides diferentes sobre el mismo conjunto base, y el objetivo es particionar el conjunto base en k subconjuntos, de modo que cada subconjunto i sea un conjunto independiente en el matroide i . Sujeto a esta restricción, se debe minimizar alguna función objetivo. En una generalización de esta variante, cada uno de los k matroides tiene un peso, y la función objetivo depende de los pesos (peso máximo, peso mínimo o suma de pesos).

Referencias

1. Scheinerman, Edward R. ; Ullman, Daniel H. (1997), "5. Arboricidad fraccionaria y métodos matroides", Teoría de grafos fraccionarios , Wiley-Interscience Series in Discrete Mathematics and Optimization, Nueva York: John Wiley & Sons Inc., págs. 99-126, ISBN 0-471-17864-0, Sr.  1481157.
2. Nash-Williams, C. St. JA (1964), "Descomposición de grafos finitos en bosques", Journal of the London Mathematical Society , 39 (1): 12, doi :10.1112/jlms/s1-39.1.12, MR  0161333.
3. Edmonds, Jack (1965), "Partición mínima de un matroide en subconjuntos independientes" (PDF) , Journal of Research of the National Bureau of Standards , 69B : 67–72, doi : 10.6028/jres.069b.004 , MR  0190025.
4. Gabow, Harold N. ; Westermann, Herbert H. (1992), "Bosques, marcos y juegos: algoritmos para sumas matroidales y aplicaciones", Algorithmica , 7 (5–6): 465–497, doi :10.1007/BF01758774, MR  1154585.
5. Cunningham, William H. (1 de noviembre de 1986). "Límites mejorados para algoritmos de partición e intersección de matroides". Revista SIAM de Computación . 15 (4): 948–957. doi :10.1137/0215066. ISSN  0097-5397.
6. Edmonds, Jack (1970), "Funciones submodulares, matroides y ciertos poliedros", Estructuras combinatorias y sus aplicaciones (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) , Nueva York: Gordon y Breach, págs. 69-87, MR  0270945.