Existe um algoritmo eficiente para esse problema de cobertura do ciclo de vértices?

Eu tenho tentado encontrar um algoritmo para encontrar uma cobertura máxima de ciclo de vértice de um gráfico direcionado - ou seja, um conjunto de ciclos disjuntos que contêm todos os vértices em G , com o maior número possível de ciclos (não consideramos vértices individuais circulam aqui). Eu sei que o problema de encontrar uma cobertura mínima de ciclo de vértice, bem como encontrar uma cobertura de ciclo de vértice com exatamente k ciclos é NP-completo. Mas e o caso máximo?$G$$G$$k$

Embora eu ache uma resposta interessante em geral, os gráficos para os quais eu quero usá-lo são realmente bastante limitados por sua construção; talvez, mesmo que o problema seja NP-complete, possa haver uma solução polinomial para essas instâncias específicas.

Temos uma lista de números inteiros , elementos l i e vamos usar S , elementos s i para se referir a L após a triagem. Como um exemplo:$L$$l_i$$S$$s_i$$L$

Os vértices do gráfico serão identificados com pares modo que l i = n e s i ≠ n . O gráfico possui uma aresta direcionada ( n , i ) → ( m , j ) se e somente se s j = n . (Um ciclo neste gráfico corresponde a um conjunto de valores que podem ser permutados ciclicamente, de forma que eles acabem na posição classificada.)$(n, i)$$l_i = n$$s_i \neq n$$(n, i) \rightarrow (m, j)$$s_j = n$

O exemplo acima produziria o seguinte gráfico (usando índices baseados em 1):

Uma coisa que não funciona é a abordagem gananciosa de remover repetidamente o menor ciclo (como mostra este exemplo).

Observe que esse problema é (se eu não cometi nenhum erro) equivalente a perguntar quantos swaps você precisa para classificar uma determinada lista. (Foi isso que inspirou a análise desse problema em primeiro lugar.)

$|C|-1$$|C|$$-1$.) Ou seja, o peso depende do tamanho do ciclo, não das arestas específicas que ele inclui. Mas talvez isso dê a alguém outra idéia de como reduzir o problema.

Parece também que limitar o tamanho dos ciclos torna o problema difícil para APX em gráficos gerais. Isso não implica necessariamente que o mesmo seja verdade para a tarefa de maximizar o número de ciclos, nem para os gráficos específicos em consideração aqui, mas parece estar suficientemente relacionado que pode ser importante.

Em resumo: Pode-se encontrar uma cobertura máxima do ciclo separado de vértices para os gráficos construídos a partir do processo acima?

Além disso, eu também estaria interessado em saber se a cobertura máxima do ciclo separado de vértices também possui uma solução eficiente para gráficos arbitrários que admitem pelo menos uma cobertura de ciclo (que provavelmente cairá como resposta à pergunta principal) ou se apenas determinar o número de ciclos na cobertura máxima (em oposição às arestas reais contidas em cada uma) torna o problema mais simples. Fico feliz em publicá-las como perguntas separadas, se as pessoas acharem que merecem respostas completas por conta própria.

$G$$k$$k=2$$k=3$ $k$$k$

$G$$G$$((3/5)-\epsilon)$$\epsilon > 0$

Para detalhes e provas das reivindicações acima, consulte [1].

[1] Bläser, Markus e Bodo Manthey. "Dois algoritmos de aproximação para coberturas de 3 ciclos." Algoritmos de aproximação para otimização combinatória. Springer Berlin Heidelberg, 2002. 40-50.