Particionamiento de matroides

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 , es decir, el número mínimo de bosques necesarios para cubrir todas sus aristas. La partición de matroides puede resolverse en tiempo polinomial , dado un oráculo de independencia para el matroide. Puede generalizarse para demostrar 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 mayor conjunto independiente común en la intersección de dos matroides dados. ^{[ 1 ]}

La arboricidad de un grafo no dirigido es el número mínimo de bosques en los que se pueden particionar sus aristas, o equivalentemente (añadiendo aristas superpuestas a cada bosque según sea necesario) el número mínimo de bosques generadores 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${\displaystyle H}$del gráfico dado${\displaystyle G}$, de la cantidad${\displaystyle \left\lceil {\frac {|E(H)|}{|V(H)|-1}}\right\rceil }$. ^{[ 2 ]}

Los bosques de un grafo forman los conjuntos independientes del matroide gráfico asociado y la cantidad${\displaystyle |V(H)|-1}$En la fórmula de Nash-Williams aparece el rango del matroide gráfico de${\displaystyle H}$, 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 de matroides para el matroide gráfico. El hecho de que el${\displaystyle |E(H)|}$Los elementos de este matroide no pueden ser particionados en menos de${\displaystyle {\frac {|E(H)|}{|V(H)|-1}}}$subconjuntos independientes es entonces simplemente una aplicación del principio del palomar que dice que, si${\displaystyle x}$Los elementos se dividen en conjuntos de tamaño como máximo${\displaystyle y}$, entonces al menos${\displaystyle x/y}$Se necesitan conjuntos. La dirección más difícil de la fórmula de Nash-Williams, que puede generalizarse a todos los matroides, es la demostración de que siempre existe una partición de este tamaño. ^{[ 1 ]}

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

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

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

El primer algoritmo para la partición de matroides fue dado por Edmonds (1965) . ^{[ 3 ]} Es un algoritmo de camino de aumento incremental 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 el momento. En cada paso, al considerar un elemento${\displaystyle x}$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 han sido particionados, el nuevo elemento${\displaystyle x}$y un elemento especial${\displaystyle \bot _{i}}$para cada uno de los${\displaystyle k}$conjuntos independientes en la partición actual. Luego forma un grafo dirigido.${\displaystyle G_{x}}$en este conjunto de nodos, con un arco dirigido${\displaystyle \bot _{i}\rightarrow y}$para cada elemento matroide${\displaystyle y}$que se puede agregar al conjunto de particiones${\displaystyle i}$sin provocar que se vuelva dependiente y con un arco dirigido${\displaystyle z\rightarrow y}$para cada par de elementos matroides${\displaystyle (y,z)}$de tal manera que la eliminación${\displaystyle z}$de su partición y reemplazándola con${\displaystyle y}$forma otro conjunto independiente. ^{[ 1 ] [ 3 ]}

Ahora bien, hay dos casos:

• Si este gráfico contiene una ruta dirigida desde un elemento${\displaystyle \bot _{i}}$al elemento recientemente considerado${\displaystyle x}$, entonces el camino más corto de este tipo (o más generalmente cualquier camino que no tenga aristas de atajo) describe una secuencia de cambios que se pueden hacer simultáneamente a los conjuntos de partición para formar una nueva partición, con el mismo número de conjuntos, que también incluye${\displaystyle x}$En este caso, el algoritmo realiza estos cambios y continúa.
• Si, por otro lado, no existe tal camino, entonces${\displaystyle S}$constan de los elementos matroides a partir de los cuales${\displaystyle x}$es alcanzable en${\displaystyle D}$Cada conjunto en la partición actual debe ser un conjunto independiente maximal en la restricción.${\displaystyle M|S}$, porque si algún elemento${\displaystyle y}$de${\displaystyle S}$podría agregarse al conjunto de particiones${\displaystyle i}$En la restricción, entonces existiría un arco${\displaystyle \bot _{i}\rightarrow y}$(si se establece la partición${\displaystyle i}$no es máximo en el matroid completo${\displaystyle M}$) o un arco${\displaystyle z\rightarrow y}$dónde${\displaystyle z\notin S}$(si el conjunto de partición no es máximo en${\displaystyle S}$pero máximo en el matroide completo). En cualquier caso, la existencia de este arco contradice la construcción supuesta del conjunto${\displaystyle S}$y la contradicción demuestra que cada conjunto de partición es maximal. Por lo tanto, siguiendo la sencilla dirección de la fórmula de partición de matroides, el número de conjuntos necesarios para la partición es...${\displaystyle S}$es al menos

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

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

El algoritmo general, entonces, considera cada elemento.${\displaystyle x}$a partir del matroide dado, a su vez, construye el grafo${\displaystyle G_{x}}$, prueba qué nodos pueden alcanzar${\displaystyle x}$y utiliza esta información para actualizar la partición actual de modo que incluya${\displaystyle x}$En cada paso, la partición de los elementos considerados hasta el momento es óptima, por lo que cuando el algoritmo finaliza habrá encontrado una partición óptima para todo el matroide. Para demostrar la corrección de este algoritmo, es necesario demostrar que un camino libre de atajos en el grafo auxiliar siempre describe una secuencia de operaciones que, al realizarse simultáneamente, preserva correctamente la independencia de los conjuntos en la partición; Edmonds proporcionó una demostración de este hecho. Dado que el algoritmo solo aumenta el número de conjuntos en la partición cuando la fórmula de partición del matroide indica que se necesita un número mayor, la corrección de este algoritmo también demuestra la corrección de la fórmula. ^{[ 1 ] [ 3 ]}

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 ]}

Una suma de matroides${\displaystyle \sum _{i}M_{i}}$(donde cada${\displaystyle M_{i}}$es un matroide) es en sí mismo un matroide, teniendo como elementos la unión de los elementos de los sumandos. Un conjunto es independiente en la suma si puede particionarse 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 de matroides. Su corrección puede usarse para probar que una suma de matroides es necesariamente un matroide. ^{[ 3 ] [ 4 ]} Un problema extendido, que a veces también se llama partición de matroides , es encontrar el conjunto más grande que sea independiente en la suma de matroides, es decir, el conjunto más grande que pueda particionarse en conjuntos que sean disjuntos en cada matroide de entrada. Cunningham ^{[ 5 ]} presenta un algoritmo para resolver este problema en O ( n ) n -matroides de elementos usando${\displaystyle O(n^{2.5})}$Llamadas a un oráculo de la independencia .

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

La partición de matroides es una forma del problema de cobertura de conjuntos , y el problema de empaquetamiento de conjuntos correspondiente (encontrar el número máximo de conjuntos generadores disjuntos dentro de un matroide dado) también es de interés. Se puede resolver 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 a 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 se pueden resolver en tiempo polinomial utilizando métodos de partición de matroides. ^{[ 1 ]}

Además de su uso en el cálculo de la arboricidad de un grafo, la partición de matroides puede utilizarse con otros matroides para encontrar un subgrafo de un grafo dado cuyo grado promedio sea máximo, y para encontrar la robustez de las aristas de un grafo (una variante de la robustez de grafos 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 (el número de subconjuntos en la partición) es fijo. Existen 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).