¿Existe un algoritmo eficiente para este problema de cobertura de ciclo de vértice?

23

He estado tratando de encontrar un algoritmo para encontrar la cobertura máxima del ciclo de vértices de un gráfico dirigido , es decir, un conjunto de ciclos disjuntos que contienen todos los vértices en , con tantos ciclos como sea posible (no consideramos ciclos de vértices individuales aquí). Sé que el problema de encontrar una cubierta de ciclo de vértice mínimo , así como encontrar una cubierta de ciclo de vértice con exactamente ciclos es NP-completo. ¿Pero qué pasa con el caso máximo?GGk

Si bien encontraría una respuesta a esto interesante en general, las gráficas para las que quiero usar esto en realidad están bastante limitadas por su construcción, por lo que tal vez incluso si el problema es NP-completo podría haber una solución polinómica para estas instancias específicas.

Tenemos una lista de enteros , elementos y usaremos , elementos para referirnos a después de ordenarlo. Como ejemplo:LliSsiL

L=(1,3,2,5,0,7,4,2,6,0,8,1)S=(0,0,1,1,2,2,3,4,5,6,7,8)

Los vértices de la gráfica serán identificados con los pares de tal manera que y . El gráfico tiene una arista dirigida si y solo si . (Un ciclo en este gráfico corresponde a un conjunto de valores que pueden permutarse cíclicamente para que terminen en su posición ordenada).(n,i)li=nsin(n,i)(m,j)sj=n

El ejemplo anterior arrojaría el siguiente gráfico (usando índices basados ​​en 1):

ingrese la descripción de la imagen aquí

Una cosa que no funciona es el enfoque codicioso de eliminar repetidamente el ciclo más pequeño (como muestra este ejemplo).

Tenga en cuenta que este problema es (si no cometí ningún error) equivalente a preguntar cuántos intercambios necesita para ordenar una lista determinada . (En primer lugar, lo que inspiró a investigar este problema).

Después de algunos consejos de la respuesta de Juho y un poco más de lectura en la literatura, me he encontrado con el problema de asignación que parece estar muy relacionado. Sin embargo, el problema de asignación se formula en términos de un gráfico bipartito ponderado y hasta ahora no he podido encontrar una manera de elegir aristas y pesos para reducir este problema. Si quisiéramos formular el problema aquí en términos de minimizar una función de peso, entonces un enfoque intuitivo sería decir que el peso de cada ciclo es dondees el número de aristas (o vértices) en el ciclo. (Por supuesto, esto es equivalente a simplemente establecer el peso en|C|1|C|1.) Es decir, el peso depende del tamaño del ciclo, no de los bordes particulares que incluye. Pero tal vez esto le da a alguien otra idea sobre cómo reducir el problema.

También parece que limitar el tamaño de los ciclos hace que el problema sea difícil para los gráficos generales. Esto no implica necesariamente que lo mismo sea cierto para la tarea de maximizar el número de ciclos, ni para los gráficos específicos que se consideran aquí, pero parece estar lo suficientemente relacionado como para que pueda ser importante.

En resumen: ¿se puede encontrar una cobertura máxima de ciclo disjunto de vértice para los gráficos construidos a partir del proceso anterior?

Como dos aspectos, también me interesaría saber si la cobertura máxima del ciclo disjunto del vértice también tiene una solución eficiente para gráficos arbitrarios que admitan al menos una cobertura del ciclo (que probablemente caerá como respuesta a la pregunta principal), o si solo determinar el número de ciclos en la cobertura máxima (en oposición a los bordes reales contenidos en cada uno) simplifica el problema. Me complace publicarlas como preguntas separadas si las personas creen que merecen respuestas completas por su cuenta.

Martin Ender
fuente
¿Has mirado la literatura de CS sobre intercambios renales? El problema parece estar relacionado, por lo que me pregunto si alguno de los métodos allí se puede aplicar a este. Sin embargo, esto podría ser un callejón sin salida ...
DW
@DW No lo he hecho (no sabía que era una cosa). Veré qué puedo encontrar, gracias.
Martin Ender
el problema es de hecho similar a los intercambios renales estudiados desde un punto de vista teórico, por ejemplo, este artículo de Roughgarden explica que se prefieren los ciclos pequeños por razones casi obvias (p3); los tamaños de los ciclos implican "operaciones simultáneas" y los más pequeños disminuyen el riesgo de llevar a cabo todas las operaciones con complicaciones o los donantes cambian de opinión, etc.
vzn
@AustinMohr Creo que los gráficos obtenidos de la construcción que describo siempre serán descomponibles en ciclos (y, además, no importa qué ciclo elimines, el resto seguirá siendo descomponible en ciclos). Si también desea abordar gráficos generales, suponga que existe al menos una cubierta completa.
Martin Ender
@ MartinBüttner En su caso específico, si todos los elementos de la lista son distintos, ¿su problema sería equivalente a encontrar la descomposición (única) del ciclo de la permutación ?
mhum

Respuestas:

4

Deje que una cubierta de ciclo de un gráfico dirigido sea una colección de ciclos de vértice disjunto de tal manera que cada vértice esté exactamente en un ciclo. Entonces, si te entiendo correctamente, dado un gráfico dirigido , quieres una cobertura máxima del ciclo, donde cada ciclo tiene una longitud de al menos (tal vez para , o al menos). Una cubierta de ciclo donde cada ciclo tiene una longitud de al menos se llama cubierta de ciclo .Gkk=2k=3 kk

Decidir si un dígrafo tiene una cubierta de 2 ciclos es solucionable en tiempo polinómico. El problema de decidir si tiene una cobertura de 3 ciclos es NP-completo. El problema de optimización correspondiente (es decir, encontrar una cubierta de 3 ciclos de peso máximo) es APX-complete, y tiene un algoritmo de aproximación (para cualquier ). La buena noticia aquí es que también se puede calcular un peso máximo de 2 ciclos de cobertura en tiempo polinómico (siempre que los pesos de los bordes no sean negativos).GG((3/5)ϵ)ϵ>0

Para obtener detalles y pruebas de las afirmaciones anteriores, consulte [1].


[1] Bläser, Markus y Bodo Manthey. "Dos algoritmos de aproximación para cubiertas de 3 ciclos". Algoritmos de aproximación para la optimización combinatoria. Springer Berlin Heidelberg, 2002. 40-50.

Juho
fuente
Interesante, intentaré seguir las referencias de ese artículo. Gracias. (Debí haber leído mal algo cuando pensé que las cubiertas de k-ciclos eran cubiertas con exactamente k ciclos. O tal vez esa es una definición diferente utilizada en otros lugares.)
Martin Ender
2
@ MartinBüttner Por cierto, es probable que desee echar un vistazo a la tesis doctoral de Bläser aquí . (Está en alemán, pero es probable que no tenga ningún problema con eso :-)). Debe cubrir los detalles de calcular realmente una cubierta de 2 ciclos de peso máximo.
Juho
Ah, espera, en realidad estoy buscando una cobertura de 2 ciclos de peso mínimo (como en, una que tiene una cantidad máxima de ciclos, ya que el peso será donde es el número de ciclos en la tapa). (Todavía estoy leyendo la tesis si eso está cubierto, y creo que sí, pero su respuesta parece centrarse en el peso máximo.)|V|nn
Martin Ender
Pensando un poco más, no estoy seguro de que sea posible formular el problema en términos de pesos. Con pesos iguales, todas las cubiertas de ciclo tienen el mismo peso. Mi "costo" para un ciclo es en realidad su longitud menos 1. Es por eso que quiero tantos ciclos como sea posible. Si esto pudiera formularse en términos de pesos, se reduce al problema de asignación, pero si no, supongo que tengo que seguir buscando.
Martin Ender