Isomorfismo del sottografo su Multi-grafici stellari con bordi etichettati

Question

Il mio approccio al problema è stato quello di riformularlo in qualcosa di più riconoscibile, ma non conosco nemmeno il modo migliore per risolvere i problemi riformulati. Elenco il problema originale, un esempio e due riformulazioni di seguito. La seconda riformulazione è equivalente a un problema di assegnazione sbilanciato con una matrice di costi binari.

Formulazione originale

ne ho due stella multigrafe: un piccolo modello, e un grande obbiettivo. I grafici possono avere più bordi tra una singola coppia di nodi. I bordi di ciascun grafico hanno etichette da una piccola serie di etichette. Sto cercando l'algoritmo più efficiente per verificare se esiste un sottografo del bersaglio che è isomorfico al modello.

Esempio

Considera il modello

e il bersaglio

Dove i colori dei bordi rappresentano le etichette. Esiste un sottografo del bersaglio costituito dai nodi 1, 2, 3 e 5 (e alcuni bordi che non ho dato nomi) che è isomorfo al grafico del pattern. Si noti che il sottografo non deve essere un sottografo indotto dal nodo e non è in questo caso.

Riformulazione 1

Enumera i vicini del centro di ogni grafico: $ 1, 2, dots n _ { mathrm {pattern}} $ e $ 1, 2, dots n _ { mathrm {target}} $. Definisci $ a_ {i, j} = 1 $ se il nodo $ i $ nell'obiettivo ha almeno più bordi di ogni tipo al centro target come il nodo $ j $ nel modello ha al centro del modello. Se il vincolo non è soddisfatto, allora $ a_ {i, j} = 0 $. Il problema diventa: data una matrice binaria $ mathbf {a} $ con più righe delle colonne, esiste una permutazione delle righe in modo tale che la diagonale principale sia tutte?

Riformulazione 2

Ti viene dato $ n _ { mathrm {target}} $ lavoratori per eseguire $ n _ { mathrm {pattern}} $ compiti, in cui ogni lavoratore è competente solo in un sottoinsieme delle attività. Esiste un incarico di lavoratori a compiti in modo tale che ogni attività abbia assegnato almeno un lavoratore competente?