Trovare più lunghe catene di dispositivi corrispondenti

Question

Set A ha n dispositivi. Set B ha dispositivi m. Alcuni dispositivi in ??A sono compatibili con i dispositivi in ??B, e alcuni dispositivi in ??B sono compatibili con quelli in A.

Voglio il maggior numero di dispositivi compatibili collegati tra loro il più possibile. (Non è necessario avere un dispositivo in A e B in B per essere reciprocamente compatibili.)

Modifica per chiarezza :. Qualsiasi dispositivo può essere collegato a 0, 1 o 2 altri dispositivi, ma non si

Infine tutti i dispositivi (o tutti solo due, se i "fini" non soddisfano) dovrebbe essere legata insieme 1 a 1. E 'possibile collegare un qualsiasi dispositivo a qualsiasi altro dispositivo. Ma nessun dispositivo in A sono compatibili con qualsiasi dispositivo in A (ma sono collegabile ), e lo stesso vale per i dispositivi in ??B.

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

Poi il grafo G

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

è un grafico ottimale.

G non deve essere ciclico, ma può essere.

Ci sono modi intelligenti per affrontare questo?

Answer 1

Credo che questo problema è NP-hard da una riduzione da non orientato problema percorso più lungo, che è noto essere NP-hard da una riduzione dal non orientato problema cammino hamiltoniano (vedi di Sipser Introduzione alla teoria della computazione per i dettagli sul perché).

Nel problema percorso più lungo non orientati, c'è dato in ingresso un grafo non orientato G = (V, E), insieme a una coppia di nodi U e V e un numero k, e vuole determinare se v'è un semplice (senza nodo appare due volte) percorso da u a v di lunghezza almeno k. Siamo in grado di convertire questo nel vostro problema utilizzando una riduzione polinomiale come segue:

• Per ogni nodo v _i ? V, è presente un dispositivo in A (chiamare d _i ).
• Per ogni bordo {v _i , v _j } ? V, è presente un dispositivo a B (chiamare e _{i, j} ).
• Per ogni nodo v _i e il bordo {v _i , v _j }, dispositivo d _i è compatibile con il dispositivo e _{i, j} .

Questa riduzione ha dimensione polinomiale, poiché il numero totale di dispositivi generati è di dimensione | V | + | E | e il numero di connessioni è 2 | E |. Inoltre, possiamo vedere che esiste un percorso di lunghezza k da v _i per v _j sul grafico G sse esiste una catena di dispositivi di lunghezza 2k + 1 da d _i per d _j . In particolare, se ((v _{i 1} , v _{i 2} ), (v _{i 2} , v _{i 3} ), ..., (v _{i k - 1} , v _{i k} )) è un cammino semplice da v _i per v _j , allora la catena d _{i 1} ? e _{i 1 , i 2} ? d < sub> i ₂ ? e _{i 2 , i 3} ? d _{i < sub> 3} ? ... ? e _{i k - 1 , i k} ? d _{i k} e viceversa. Abbiamo così una riduzione polinomiale da percorso più lungo non orientato a voi problema come segue:

• Dato come input (G, v _i , v _j , k) al problema percorso più lungo non orientati:
  • Struttura i gruppi A e B come sopra, con compatibilità C come sopra.
  • Verificare se v'è una catena di dispositivi di lunghezza 2k + 1 di d _i D _j .
  • Se è così, l'uscita "sì"
  • In caso contrario, l'uscita "no".

Questa riduzione risolve il problema percorso più lungo non orientato in tempo polinomiale non deterministico usando un risolutore per il vostro problema, e così il vostro problema è NP-hard. Di conseguenza, non si deve aspettare di trovare un algoritmo polinomiale per il vostro problema; trovare una risposta esatta è probabile che prendere tempo esponenziale a meno che P = NP.

Siamo spiacenti per dare una risposta negativa, ma spero che questo aiuti!

Answer 2

Questa è NP-difficile, ma credo che una copertura ciclo massima problema approssimazioni può aiutare (in ogni dispositivo di collegamento gruppo con bordo di dimensione 0), inoltre è possibile aggiungere qualche nodo in più, che collegato a tutti gli altri nodi, in peso, 0) , ad esempio, questo documento: Approximating Peso massimo Cycle in Directed grafici con pesi zero e uno vi aiuterà.