Положительный топологический порядок, дубль 3

20

Предположим, у нас есть матрица n на n. Можно ли изменить порядок строк и столбцов так, чтобы мы получили верхнетреугольную матрицу?

Этот вопрос мотивирован этой проблемой: положительный топологический порядок

Первоначальная проблема решения, по крайней мере, так же сложна, как эта, поэтому результат NP-полноты также решит эту проблему.

Изменить: Ласло Вег и Андрас Франк обратили мое внимание на эквивалентную проблему, заданную Гюнтером Роте: http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph

Редактировать: приведение к исходной проблеме заключается в следующем. Предположим, что DAG имеет только два уровня, они будут соответствовать строкам и столбцам матрицы. Также у нас есть один узел с весом +1. Все остальные на нижнем уровне имеют вес -1, а на верхнем уровне +1.

domotorp
источник
Как вы сводите это к первоначальной проблеме? Кстати, эта проблема выглядит интересной сама по себе.
Цуёси Ито
Вы ищете одну перестановку для применения как к строкам и столбцам, так и к двум отдельным перестановкам? Я предполагаю два, так как только с одной проблема кажется эквивалентной топологической сортировке.
Уоррен Шуди
Думая о нем как о двудольном графе (как в ссылке elte), они дают необходимое условие, чтобы у него не было подграфа, составленного из копий K2, C4, C6, C8 и т. Д. Другое необходимое условие - последовательность степеней обоих части преобладают (1, 2, 3, ..., n) - я думаю, что это сильнее, чем другие условия в клике в ссылке.
daveagp

Ответы:

12

Задача оказалась NP-полной. Вы можете прочитать более подробно здесь и здесь . Краткое содержание:

Дасгупта, Цзян, Каннан, Ли и Свидык показали, что сокращение из задачи является NP-завершенным: учитывая двудольный граф G и целое число k, решите, есть ли в G индуцированный подграф на 2k узлах, который можно расширить до быть уникально сопоставимым. Стефан Виалетт заметил, что это сводится к двудольному уникальному подходящему варианту этой задачи, если мы добавим nk изолированных узлов в оба класса.

domotorp
источник
Спасибо за ссылку на EGRES. Мне действительно нравятся открытые проблемы, особенно те, которые связаны с (идеальным) сопоставлением.
Мухаммед Аль-Туркистани
Каковы другие качественные открытые проблемные сайты (связанные с вычислительной сложностью)?
Мухаммед Аль-Туркистани
@turkistany, я не знаю других, я думаю, это также больше касается исследования операций / теории графов.
domotorp
3

Внимание: это частичный ответ, основанный на предположениях и слухах! В то время как более общая проблема Дэвида Эппштейна является NP-полной, возможно, эта проблема в P.

(AB,E)|A|=|B|=n

  • он не должен содержать 2 идеальных совпадений,
  • (1,2,...,n)

До сих пор я не смог найти ни одного примера, где график удовлетворяет этим условиям, но не соответствует UPMX. В таком случае, может быть, их достаточно. Можно доказать это следующим алгоритмом:

  1. если график имеет> 1 идеального соответствия, верните «not UPMX»
  2. если график не соответствует условию степени, верните «не UPMX»
  3. если график имеет = 1 идеальное соответствие, вернуть «UPMX»
  4. в противном случае, возможно, мы сможем показать, что это UPMX. Возможно, следующий алгоритм мог бы доказать это:
    • (n+12)2
    • найти некоторое новое ребро e, сложение которого не создает идеального соответствия и не нарушает условие степени; добавить е к графику
  5. (n+12)1

Вы можете охарактеризовать, какие новые ребра будут создавать идеальное соответствие, используя теорему Холла, и нетрудно определить, какие новые ребра будут нарушать границу степени. К сожалению, даже если это правда, что край правильного типа всегда существует, я не смог доказать это.

daveagp
источник
Не плохой подход, интересно, правда ли это.
Домоторп
3

Эта бумага, Получение треугольной матрицы независимыми перестановками столбцов- строк Фертин, Русу и Виалетт» показано, что задача является NP-полной для двоичных квадратных матриц.

Мухаммед Аль-Туркистани
источник
Это очень прискорбно, что они также доказали тот же результат независимо от нас, я думаю, мы должны были общаться лучше. Во всяком случае, я напишу им по электронной почте.
domotorp
@domotorp Та же проблема была задана в MathOverflow, и лучший ответ был в том, что он находится в "NP-limbo". mathoverflow.net/questions/191963/…
Мухаммед Аль-Тюркистани
-1

Проблема является NP-полной, но где алгоритм для ее решения? У меня есть один алгоритм, который работает на многих примерах, но я не могу доказать, что он будет работать постоянно.

ORILL_Code
источник
1
Можете ли вы охарактеризовать интересный класс графиков, на которых ваш алгоритм корректен?
РБ