Esta pergunta foi migrada do Mathematics Stack Exchange porque pode ser respondida no Computer Science Stack Exchange. Migrou há 3 anos .
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?GGGGkk
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:euLeuEuliSSsEusieuL
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 )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)
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 )(n,i)euEu= nli=nsEu≠ nsi≠n( n , i ) → ( m , j )(n,i)→(m,j)sj= nsj=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| C||C|- 1−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.
Você já consultou a literatura sobre CS sobre trocas renais? O problema parece relacionado, então eu me pergunto se algum dos métodos pode ser aplicado a este. Porém, isso pode ser um beco sem saída ...
@ DW eu não tenho (eu não estava ciente de que é uma coisa). Vou ver o que posso encontrar, obrigado.
o problema é de fato semelhante às trocas renais estudadas de um ponto de vista teórico, por exemplo, este artigo de Roughgarden explica que pequenos ciclos são preferidos por razões quase óbvias (p3); os tamanhos ciclo implica "operações simultâneas" e menores diminuir o risco de retirar todas as operações com complicações ou doadores mudando mentes etc
@AustinMohr Acredito que os gráficos obtidos a partir da construção que descrevo sempre serão decompostos em ciclos (e, além disso, não importa qual ciclo você remover, o restante ainda será decomposto em ciclos). Se você também deseja abordar gráficos gerais, suponha que exista pelo menos uma cobertura completa.
@ MartinBüttner No seu caso específico, se todos os elementos da lista forem distintos, seu problema seria equivalente a encontrar a decomposição (exclusiva) do ciclo da permutação ?
GGkkk=2k=2k=3k=3 kkkk
GGGG((3/5)−ϵ)((3/5)−ϵ)ϵ>0ϵ>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.
Interessante, tentarei seguir as referências desse artigo. Obrigado. (I deve ter interpretado mal alguma coisa quando eu pensei que as tampas de ciclo k foram cobertas com exatamente k ciclos ou talvez seja uma definição diferente usado em outro lugar..)
@ MartinBüttner A propósito, você provavelmente vai querer dar uma olhada na tese de doutorado da Bläser aqui . (Está em alemão, mas você provavelmente não terá problemas com isso :-)). Ele deve cobrir os detalhes de como calcular uma cobertura de peso máximo de 2 ciclos.
|V|−n|V|−nnn
Pensando um pouco mais, não tenho certeza se é realmente possível formular o problema em termos de pesos. Com pesos iguais, todas as coberturas de ciclo têm o mesmo peso. Meu "custo" para um ciclo é, na verdade, seu comprimento menos 1. É por isso que quero o maior número possível de ciclos. Se isso puder ser formulado em termos de pesos, reduz-se ao problema de atribuição, mas se não, acho que preciso continuar pesquisando.