Lo que está describiendo se conoce como matching problem for bipartite graphs. Sospecho que hay algo (aún no declarado) sobre el problema que hace que sea difícil de resolver. Hasta ahora, realmente no has puesto ninguna restricción sobre qué bordes se pueden usar. Suponiendo que hay ciertos bordes (no todos) disponibles, esos bordes "posibles" forman un gráfico, y los que usted decide usar forman una coincidencia máxima. Encontrar una coincidencia máxima en un gráfico es un algoritmo de tiempo polinomial, y es particularmente fácil codificar para el caso bipartito.
El título hace sonar como si las circunstancias pudieran imponer alguna circunstancia para que los bordes "disjuntos" pudieran no ser factibles ("intersecciones de borde mínimo"). Quizás desee cubrir los bordes (o 1 cubierta), es decir, que cada vértice pertenece al menos a un borde. Entonces, si las dos matrices de "vértices" son de diferente longitud, no habrá una "coincidencia perfecta", es decir, una coincidencia que también sea una cubierta. Un resultado clásico Hall's Marriage Theorem caracteriza cuando hay emparejamientos perfectos en un gráfico bipartito. Si el gráfico es regular (todos los vértices tienen el mismo grado), entonces König's Theorem nos dice que hay una coincidencia perfecta (y más).
Agregado:
Puede valer la pena indicando lo que la imagen parece que decir acerca de las restricciones en la elección de los bordes. Dos conjuntos de vértices tienen coordenadas {(i, 0) | i = 1, .., N} y {(j, 1) | j = 1, .., N}. Hay N bordes disponibles, segmentos de línea que conectan (i, 0) y (j, 1) siempre que y0 [i] = y1 [j]. Aunque la línea de asunto dice "intersecciones de borde mínimo", una solución es un subconjunto máximo de estos bordes que no admite intersecciones, una planar straight-line graph más grande contenida en un permutation graph dado.
Se relaciona con el problema de minimización de cruce de 2 niveles considerados aquí:
An Alternative Method to Crossing Minimization on Hierarchical Graphs -- P. Mutzel
"Sugerimos ... quitando el número mínimo de bordes de tal manera que la gráfica resultante es plana a nivel de k. En este documento abordamos el caso k = 2 ... [W] e abordamos el problema de extraer un subgrafo planar de 2 niveles de peso máximo en un gráfico de 2 niveles dado. Este problema es NP-hard ".
El problema actual impone un número igual de puntos en los dos conjuntos de vértices, el gráfico base es regular de grado 1, y ninguna opción está permitido en la numeración o posicionamiento de puntos. Por lo tanto, no es posible concluir que es tan difícil como el descrito en el documento anterior. Sin embargo, nos dirige a los métodos denominados de "bifurcación y enlace" para la solución exacta de dichos problemas.
Vamos a considerar los "bordes" del problema original como "nodos" de un nuevo gráfico en el que dos nodos son adyacentes si y sólo si los bordes originales se cruzan. [Este es un ejemplo de un gráfico de intersección.] El problema tal como se replanteó ahora es encontrar a maximum independent set del nuevo gráfico. Los problemas de este tipo son, en general, difíciles para NP, pero nuevamente sospechamos que el alcance de los problemas actuales puede no ser tan general.
Una razón para sospechar un algoritmo de tiempo polinómico podría existir es la disponibilidad de algoritmos de tiempo de aproximación polinómica para subconjuntos independientes máximos de grafo de intersección para colecciones finitas de conjuntos convexos planos:
Independent Set of Intersection Graphs of Convex Objects in 2D -- P. Agarwal and M Mustafa
"En este documento , presentamos algoritmos de aproximación para el problema de conjunto independiente en gráficos de intersección de segmentos de línea y objetos convexos en el plano ".
Hay otra observación acerca de lo especial de la presente problema que parece que sea resoluble en tiempo polinómico. Un circle graph es el gráfico de intersección de los segmentos de línea que se pueden dibujar como acordes de un círculo. Mediante un argumento de pertubación, los bordes de línea recta de un gráfico de permutación se pueden dibujar así, sin pérdida o introducción de intersecciones.
Ahora el problema del conjunto independiente máximo para gráficos circulares se puede resolver en tiempo polinomial. El artículo de Wikipedia vinculado anteriormente da esta referencia:
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
También encontré esta referencia en Google Books:
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
(cortesía Image: belisarius)
Esto parece relacionado con la pregunta de si un gráfico es plano y, si no, cuál es su subgrafo planar más grande. Aunque no conozco ningún algoritmo para ello. – templatetypedef
Este es un gráfico directo. ¿Quiere decir que y0 [0] está conectado a y1 [0]? Porque si y0 [0] = y1 [1] = 1 ese es un punto por lo que no puede formar un borde desde un vértice a sí mismo. Cuando dices intersecta, ¿te refieres a un camino que crea un ciclo? Por ejemplo, si caminó desde un vértice a lo largo de los bordes conectados, ¿podría regresar al vértice inicial? ¿Y este problema es encontrar todos los ciclos, independientemente de si están conectados entre sí? – chubbsondubs
@chubbard, no, por intersección, estaba implicando una intersección de línea geométrica.Y no, 'y0 [0]' no está conectado a 'y1 [0]' ... – st0le