Quello che viene descritto è noto come matching problem for bipartite graphs. Sospetto che ci sia qualcosa (ancora non dichiarato) sul problema che lo rende difficile da risolvere. Finora non hai posto alcuna restrizione su quali bordi possono essere usati. Supponendo che ci siano alcuni bordi (non tutti) disponibili, quei bordi "possibili" formano un grafico, e quelli che decidi di usare formano un matching massimo. Trovare una corrispondenza massima in un grafico è un algoritmo del tempo polinomiale ed è particolarmente facile codificarlo per il caso bipartito.
Il titolo fa sembrare che le circostanze possano imporre qualche circostanza in modo tale che i bordi "disgiunti" potrebbero non essere fattibili ("intersezioni minime"). Forse vuoi la copertura del bordo (o 1 copertina), cioè che ogni vertice appartiene ad almeno un bordo. Quindi, se i due array "vertex" sono di lunghezza diversa, non ci sarà un "matching perfetto", cioè un matching che è anche una cover. Un risultato classico Hall's Marriage Theorem si caratterizza quando ci sono abbinamenti perfetti in un grafico bipartito. Se il grafico è regolare (tutti i vertici hanno lo stesso grado), allora König's Theorem ci dice che c'è corrispondenza perfetta (e altro).
Aggiunto:
Può valere la pena affermando ciò che il quadro sembra dire circa le restrizioni sui bordi che scelgono. Due serie di vertici hanno coordinate {(i, 0) | i = 1, .., N} e {(j, 1) | j = 1, .., N}. Ci sono N bordi disponibili, segmenti di linea che collegano (i, 0) e (j, 1) ogni volta che y0 [i] = y1 [j]. Sebbene la riga dell'oggetto indichi "intersezioni minime", una soluzione è un sottoinsieme massimo di questi bordi che non ammette intersezioni, una più grande planar straight-line graph contenuta in un dato permutation graph.
Esso è legato alla 2-livello problema crossing minimizzazione qui considerato:
An Alternative Method to Crossing Minimization on Hierarchical Graphs -- P. Mutzel
"Suggeriamo ... rimuovendo il numero minimo di bordi in modo tale che il grafico risultante è a livello k planare. .. In questo articolo affrontiamo il caso k = 2 ... [W] e indirizzo il problema di estrarre un sottografo planare di 2 livelli di peso massimo in un dato grafico a 2 livelli.Questo problema è NP-difficile. "
Il problema presente impone un numero uguale di punti nei due gruppi di vertici, il grafico di base è regolare di grado 1 e non è consentita alcuna scelta nella numerazione o nel posizionamento dei punti. Quindi non è possibile concludere che sia così difficile come quello descritto nel documento sopra. Tuttavia, ci indirizza ai cosiddetti metodi "ramificati e vincolati" per la soluzione esatta di tali problemi.
Consideriamo i "bordi" del problema originale come "nodi" di un nuovo grafico in cui due nodi sono adiacenti se i bordi originali si intersecano. [Questo è un esempio di un grafico di intersezione.] Il problema come riesposto è ora di trovare a maximum independent set del nuovo grafico. I problemi di questo tipo sono in generale NP-difficili, ma ancora una volta sospettiamo che l'estensione dei problemi attuali potrebbe non essere così generale.
Una ragione di sospettare un algoritmo polinomiale potrebbe esistere è la disponibilità di algoritmi tempo polinomiale per massimi sottoinsiemi indipendenti di grafici intersezione per collezioni finite di insiemi convessi planari:
Independent Set of Intersection Graphs of Convex Objects in 2D -- P. Agarwal and M Mustafa
"In questo documento , presentiamo algoritmi di approssimazione per il problema dei set indipendenti sui grafici di intersezione di segmenti di linea e oggetti convessi nel piano. "
C'è un'ulteriore osservazione sulla particolarità del problema attuale che sembra risolverlo in tempo polinomiale. A circle graph è il grafico di intersezione di segmenti di linea che possono essere disegnati come accordi di un cerchio. Con un argomento di pertubazione i bordi rettilinei di un grafico di permutazione possono essere disegnati in tal modo, senza perdita o introduzione di intersezioni.
Ora il problema di impostazione indipendente massimo per i grafici a cerchio può essere risolto in tempo polinomiale. L'articolo di Wikipedia linkato sopra dà questo riferimento:
Nash, Nicholas; Gregg, David (2010), "An output sensitive algorithm for computing a maximum independent set of a circle graph", Information Processing Letters 116 (16): 630–634
ho trovato anche questo riferimento in Google Libri:
Valiente, Gabriel (2003), "A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs", Algorithms and computation: 14th Symposium, ISAAC 2003 Kyoto
(cortesia Image: Belisarius)
Questo sembra collegato alla domanda se un grafico è planare e, in caso contrario, quale è il suo più grande sottografo planare. Non conosco alcun algoritmo per questo, comunque. – templatetypedef
Questo è un grafico diretto. Intendi che y0 [0] è connesso a y1 [0]? Perché se y0 [0] = y1 [1] = 1 questo è un punto in modo da non poter formare un bordo da un vertice a se stesso. Quando dici "intersezione" intendi un percorso che crea un ciclo? Ad esempio, se camminassi da un vertice lungo i bordi collegati potresti tornare al vertice iniziale? E questo problema è trovare tutti i cicli a prescindere se sono collegati tra loro? – chubbsondubs
@ chubbard, no, per intersezione, stavo implicando un'intersezione di linee geometriche.E no, 'y0 [0]' non è connesso a 'y1 [0]' ... – st0le