Порождённое паросочетание

Порождённое или строгое паросочетание — это подмножество рёбер неориентированного графа, которые не имеют общих вершин (то есть, это паросочетание) и все рёбра, соединяющие вершины этого паросочетания, принадлежат рассматриваемому подмножеству (то есть, это порождённый подграф).

Порождённое паросочетание можно описать также как независимое множество в квадрата рёберного графа данного графа^[1].

Минимальное число порождённых паросочетаний, на которые могут быть разбиты рёбра графа, называется сильным хроматическим индексом по аналогии с хроматическим индексом графа, минимальным числом паросчетаний, на которые рёбра могут быть разбиты^[2]. Данное число равно хроматическому числу квадрата рёберного графа. Теорема Брукса, применённая к квадрату рёберного графа, показывает, что сильный хроматический индекс не превосходит квадрата максимальной степени исходного графа, но лучшие постоянные множители в квадратичной оценке могут быть получены другими методами^[3].

Проблема Ружи – Семереди касается плотности рёбер сбалансированных двудольных графов с линейным сильным хроматическим индексом. Эквивалентно, проблема касается плотности других классов графов, локально линейных графов, в которых окрестность каждой вершины является порождённым паросочетанием^[4]. Ни один из этих типов графов не может иметь квадратичного числа рёбер, но известны конструкции для графов этого типа с почти квадратичным числом рёбер^[5].

Поиск порождённого паросочетания с размером как минимум ${\displaystyle k}$ является NP-полной задачей (а тогда поиск порождённого паросочетания максимального размера NP-труден). Поиск может быть осуществлён за полиномиальное время в хордальных графах, поскольку квадраты рёберных графов хордальных графов являются совершенными графами^[6]. Более того, поиск в хордальных графах может быть осуществлён за линейное время^[7]. Если не произойдет неожиданного коллапса полиномиальной иерархии, наибольшее индуцированное паросочетание нельзя будет аппроксимировать с коэффициентом аппроксимации лучше, чем ${\displaystyle n^{1-\varepsilon }}$ за полиномиальное время^[8].

Задача также является W[1]-трудной, что означает, что даже поиск малого порождённого паросочетаниязаданного размера ${\displaystyle k}$ вряд ли имеет алгоритм с существенно большей скоростью выполнения, чем полный перебор всех ${\displaystyle k}$-наборов рёбер^[9]. Однако, задача поиска ${\displaystyle k}$ вершин, удаление которых оставляет неизменным порождённое паросочетание, является фиксированно-параметрически разрешимой задачей^[10]. Задача может быть решена точно на графах с ${\displaystyle n}$ вершинами за время ${\displaystyle O(1{,}3752^{n})}$ с экспоненциальным пространством, или за время ${\displaystyle O(1{,}4231^{n})}$ с полиномиальным пространством.^[11]

• Порождённый путь