Ponderação equilibrada das arestas no gráfico de cactos

7

Dado um cacto , queremos ponderar suas bordas de tal maneira que

  1. Para cada vértice, a soma dos pesos das arestas incidentes no vértice não passa de 1.
  2. A soma de todos os pesos das arestas é maximizada.

Claramente, a resposta não passa de para vértices ( que é a soma de um vértice e é a soma de todas as arestas). Esse limite é possível para gráficos de ciclo ponderando cada aresta 1/2.n2ndi=2DdiD

Encontrei um algoritmo ganancioso para árvores. Apenas atribua 1 às arestas incidentes às folhas e remova-as e seus vizinhos do gráfico em passes repetidos. Isso reduz o cacto a vários ciclos interconectados. Nesse ponto, eu assumi que os ciclos restantes não estavam interconectados e pesei cada extremidade 1/2. Isso obteve 9/10 casos de teste, mas é, obviamente, incompleto.

Então, como podemos resolver esse problema para os cactos em geral? Eu preferiria dicas a soluções completas, mas qualquer uma delas está bem.

Esta pergunta envolve um problema de um InterviewStreet CompanySprint . Eu já competi, mas gostaria de algumas reflexões sobre um problema (as soluções não são liberadas e tenho batido minha cabeça contra a parede por causa desse problema).

dysonsfrog
fonte
Parece que isso deve poder ser resolvido com fluxo máximo, dadas as restrições de capacidade de 1 nos vértices. Você (I) só precisa descobrir como adicionar uma fonte e afundar corretamente.
Nicholas Mancuso
Pensei nisso, mas não consegui encontrar nenhuma rede que funcionasse. Como observa sxu, uma boa solução quase certamente envolve a estrutura dos gráficos de cactos. Estou tendo dificuldades para ver como usá-lo para construir a rede. E o fato de ter encontrado uma solução para as árvores (pelo menos acho que encontrei; só esboçei uma prova para os gananciosos que não incluí aqui) me afastou da rota do LP.
Disonsfrog
Opa Peido de cérebro. Entendo agora o que você quer dizer. Isso parece promissor.
Disonsfrog
Meu próximo palpite seria atribuir onde é um vértice de articulação (participa de pelo menos 2 ciclos separados). Remova e suas bordas, depois enxágue e repita. Eventualmente, isso deixará você com componentes completamente disjuntos. 1/divivi
Nicholas Mancuso
Sim. O bom é que, com ciclos de comprimento ímpar, você pode alternar os pesos , , ... e contornar o mesmo limite . Parece bom intuitivamente, mas ainda não é uma solução completa. 1/di11/din2
Disonsfrog

Respostas:

5

Então essa pergunta está me incomodando: por que um cacto, se já existe um algoritmo de tempo linear para uma classe mais geral?

O problema primordial é conhecido como problema de correspondência fracionária e, sem surpresa, também foi estudado. Balinski (cujo resultado me foi conhecido através do livro de Schrijver, Combinatorial Optimization) caracterizou os pontos extremos do pólipo de correspondência fracionária como consistindo em uma correspondência inteira mais a metade de uma coleção de ciclos ímpares. Dados os limites de entrada relativamente baixos, suspeito que a solução pretendida para o problema era modificar o algoritmo de flor de Edmonds de uma maneira que, por enquanto, deixarei para você descobrir. A estrutura dos ciclos em um cacto torna esse algoritmo simples o suficiente para ser apropriado para uma competição.


Como sxu aponta, esse problema é passível de programação linear. Se você precisar apenas do valor objetivo, o LP duplo terá o mesmo valor objetivo e será o problema fracionário da cobertura de vértices. O bom da capa de vértice é que ela possui um ótimo meio integral; em tempo linear, você pode usar a pesquisa em profundidade para calcular uma decomposição em árvore do cacto de largura O (1) e resolver o LP duplo com um programa dinâmico que tenta valores variáveis ​​em {0, 1/2, 1}.

Se você realmente precisa de uma solução para o primal, a negligência complementar pode ajudar, mas não posso deixar de suspeitar que a restrição aos cactos deve permitir uma solução mais elementar.

Herm
fonte
1

Você sempre pode usar a programação linear : basta criar uma variável para cada aresta e uma restrição para cada vértice. No entanto, deve haver uma solução melhor, pois isso não usa o fato de termos um gráfico de cacto. Também sugiro executar algoritmos LP em alguns exemplos e tentar ver se algo interessante está acontecendo no gráfico de cactos, mas não nos gráficos gerais.

sxu
fonte