Ciclo del peso massimo in un grafico

Question

Dato un grafico ponderato (diretto o non diretto) ho bisogno di trovare il ciclo del grafico con il peso massimo.

Il peso di un ciclo è la somma del peso dei bordi del grafico.

Può essere qualsiasi ciclo, non ciclo solo di base per i quali siamo in grado di

• trovare tutto il ciclo di base (vedi Algorithms to Identify All the Cycle Bases in a UnDirected Graph)
• calcolare il peso di ciascun ciclo di base e trovare il massimo

Potrei provare a enumerare tutti i cicli del grafico e quindi calcolare il massimo ma il numero totale di cicli può essere veramente grande (se il grafico è completo allora qualsiasi sequenza di vertici in cui il primo e l'ultimo sono identici è un ciclo) .

Avete qualche idea di trovare quel ciclo di peso massimo senza enumerare tutti i cicli?

Se è necessaria un'ipotesi sul grafico (pesi positivi ad esempio), si prega di indicarli.

Answer 1

Questo è NP-Hard.

Il problema del ciclo Hamiltoniano può essere ridotto a questo.

Dato un grafico per il quale è necessario verificare se esiste o meno un ciclo hamiltoniano, assegnare il peso 1 a ciascun bordo.

Ora eseguire l'algoritmo per ottenere il ciclo di peso massimo. Se il peso è < n, allora il grafico originale non ha ciclo Hamiltoniano, altrimenti lo fa.

Answer 2

Se è possibile trovare il percorso ponderato minimo nel caso specifico, è sufficiente invertire i segni di tutti i pesi e applicare l'algoritmo. Ovviamente stai facendo delle ipotesi non dichiarate perché l'argomento di Moron è corretto (nessun gioco di parole). Le ipotesi che stai facendo potrebbero essere pesi positivi o nessun ciclo di peso negativo. Penso che dovresti fare uno sforzo per dichiararli invece di lasciare che le persone cerchino nello spazio infinito di possibili ipotesi. Per quanto riguarda i risultati di durezza, anche questo è difficile da approssimare in un certo numero di modi, controlla this paper. Lo stesso documento contiene diversi risultati positivi per importanti tipi di grafici, ma riguarda i percorsi non pesati più lunghi, quindi la mia ipotesi è che la maggior parte degli algoritmi nella carta non aiuti direttamente nel tuo caso. Se cerchi "Heavy cycles" troverai una serie di documenti interessanti, ma hanno un carattere più matematico. Se i pesi sono numeri interi piccoli (fino a un polinomio nella dimensione del grafico), puoi provare a sostituire ogni spigolo con un percorso non pesato per ridurre il problema al caso non ponderato. Spero che questo aiuti in una certa misura, ma potresti avere un problema di ricerca aperto sulle tue mani.