Задача двудольной реализации

Задача двудольной реализации — это классическая задача разрешимости в теории графов. Даны две конечные последовательности натуральных чисел $(a_{1},\dots ,a_{n})$ и $(b_{1},\dots ,b_{n})$, спрашивается, существует ли простой двудольный граф такой, что $(a_{1},\dots ,a_{n}),(b_{1},\dots ,b_{n})$ являются последовательностями степеней этого двудольного графа.

Решения

Задача принадлежит классу сложности P. Согласно теореме Гейла — Райзера, для решения данной задачи нужно проверить, что ${\textstyle \sum \limits _{i=1}^{n}a_{i}=\sum \limits _{i=1}^{n}b_{i}}$, а также что для каждого $k\leq n$ верно, что ${\textstyle \sum \limits _{i=1}^{k}a_{i}\leq \sum \limits _{i=1}^{n}\min(b_{i},k)}$.

В других обозначениях

Задача может быть поставлена в терминах матриц из нулей и единиц. Если такой двудольный граф существует, то у его матрицы бисмежности суммы столбцов и суммы строк соответствуют $(a_{1},\ldots ,a_{n})$ и $(b_{1},\ldots ,b_{n})$. Таким образом, задача может быть сформулирована как поиск 0-1-матрицы для данных сумм столбцов и строк. В классической литературе задача иногда формулируется в терминах таблиц сопряжённости как задача поиска таблицы сопряжённости с заданными маргинальными частотами. Ещё одна формулировка задачи возможна в терминах последовательностей степеней простых ориентированных графов с не более чем одной петлёй в каждой вершине. В этом случае матрица интерпретируется как матрица смежности такого ориентированного графа, и задача формулируется так: «Верно ли, что пары неотрицательных чисел $((a_{1},b_{1}),\dots ,(a_{n},b_{n}))$ соответствуют парам полустепеней захода и исхода некоторого ориентированного графа с не более чем одной петлёй в каждой вершине?»

Связанные задачи

Аналогичные задачи описывают последовательности степеней простых графов и простых ориентированных графов. Соответствующие задачи известны как задача о реализации графа и задача реализации ориентированного графа.

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

Задача равномерной выборки двудольного графа с фиксированной последовательностью степеней заключается в построении решения задачи двудольной реализации с дополнительным ограничением, что каждое такое решение получается с одной и той же вероятностью. Как показала Катерина Гринхил, эта задача принадлежит классу FPTAS для регулярных двудольных графов без 1-фактора. В дальнейшем Эрдёш с соавторами показали принадлежность данному классу для полурегулярных последовательностей. В случае произвольных двудольных графов задача остаётся нерешённой.

Литература

• Gale D. A theorem on flows in networks // Pacific J. Math.. — 1957. — Т. 7, вып. 2. — С. 1073–1082. — doi:10.2140/pjm.1957.7.1073.
• Ryser H. J. Combinatorial Mathematics. — John Wiley & Sons, 1963.
• Catherine Greenhill. A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs // Electronic Journal of Combinatorics. — 2011. — Т. 18, вып. 1. — С. 234. — . — arXiv:1105.0457.
• Erdős P.L., Kiss S.Z., Miklós I., Soukup L. Approximate Counting of Graphical Realizations // PLOS ONE. — 2015. — Т. 10, вып. 7. — С. e0131300. — doi:10.1371/journal.pone.0131300. — . — arXiv:1301.7523.
• Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. — Москва: «Наука» Главная редакция физико-математической литературы., 1965.