Ordenamiento topológico positivo, tomar 3

Supongamos que tenemos una matriz n por n. ¿Es posible reordenar sus filas y columnas de manera que obtengamos una matriz triangular superior?

Esta pregunta está motivada por este problema: ordenamiento topológico positivo

El problema de decisión original es al menos tan difícil como este, por lo que un resultado de completitud NP también lo resolvería.

Editar: Laszlo Vegh y Andras Frank llamaron mi atención sobre un problema equivalente preguntado por Gunter Rote: http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph

Editar: La reducción al problema original es la siguiente. Suponga que el DAG tiene solo dos niveles, estos corresponderán a las filas y columnas de la matriz. Además, tenemos un solo nodo con peso +1. Todos los demás en el nivel inferior tienen peso -1 y en el nivel superior +1.

El problema resultó ser NP-completo. Puedes leer más en detalle aquí y aquí . Breve resumen:

Dasgupta, Jiang, Kannan, Li y Sweedyk demostraron que la reducción es por un problema NP-completo: dado un gráfico bipartito G y un entero k, decida si G tiene una subgrafía inducida en 2k nodos que se puede extender a Ser excepcionalmente compatible. Stéphane Vialette observó que esto se reduce a la versión bipartita de coincidencia única de este problema si agregamos nk nodos aislados a ambas clases.

Atención: ¡Esta es una respuesta parcial basada en conjeturas y rumores! Mientras que el problema más general de David Eppstein es NP-completo, quizás este esté en P.

Digamos que un gráfico bipartito con es "UPMX" si es extensible a un gráfico con una coincidencia perfecta única. Estas son algunas condiciones necesarias para UPMX:| A | = | B | = $(A \cup B, E)$$|A|=|B|=n$

• no debe contener 2 combinaciones perfectas,
• la secuencia de grados de A, cuando se ordena en orden creciente, debe ser componente , y también para B. Llamaré a esto la "condición de grado".$\le (1, 2, ..., n)$

Hasta ahora, no he podido encontrar ningún ejemplo en el que un gráfico cumpla estas condiciones, pero no puede ser UPMX. En ese caso, tal vez sean suficientes. Uno podría probar esto con el siguiente algoritmo:

1. si el gráfico tiene> 1 coincidencias perfectas, devuelve "no UPMX"
2. si el gráfico falla la condición de grado, devuelve "no UPMX"
3. si el gráfico tiene = 1 coincidencia perfecta, devuelve "UPMX"
4. de lo contrario, tal vez podamos mostrar que es UPMX. Quizás el siguiente algoritmo podría probarlo:
   • mientras que el gráfico tiene bordes,$\le \tbinom{n+1}{2} - 2$
   • encuentre un nuevo borde e cuya adición no cree una coincidencia perfecta y no viole la condición de grado; agregue e al gráfico
5. ahora el gráfico tiene aristas y ninguna coincidencia perfecta, y satisface la condición de grado. Creo que no es demasiado difícil mostrar que es UPMX, por lo tanto, también lo fue el gráfico original.$\tbinom{n+1}{2} - 1$

Puede caracterizar qué nuevas aristas crearían una coincidencia perfecta utilizando el teorema de Hall, y no es difícil caracterizar qué nuevas aristas violarían el límite de grado. Desafortunadamente, incluso si es cierto que siempre existe un borde del tipo correcto, no he podido probarlo.

Este artículo, Obteniendo una matriz triangular mediante permutaciones independientes de fila-columna Fertin, Rusu y Vialette, muestra que el problema es NP-completo para matrices cuadradas binarias.

El problema es NP-complete, pero ¿dónde está el algoritmo para resolverlo? Tengo un algoritmo que funciona en muchos ejemplos, pero no puedo demostrar que vaya a funcionar todo el tiempo.