Жесткая вычислительная задача на специальном классе двудольных графов

Меня интересуют свойства класса двудольных графов где все узлы в 3-регулярны, все узлы в 2-регулярны и, Во-первых, это хорошо известный класс графиков? Во- вторых,$G(X \cup Y, E)$$X$$Y$$|X|=|2Y/3|$

Есть ли пример неразрешимой вычислительной задачи, ограниченной этим классом двудольных графов?

Имея 3-регулярный граф вы можете построить двудольный граф с необходимыми свойствами, выбирая и и для каждого ребра добавить ребра . Поэтому я думаю, что вы можете найти некоторые сложные проблемы, начиная с сложных задач на 3-регулярных графах.$G = \{V,E\}$$G'$$X = V$$Y = E$$e_k = (u_i,u_j) \in E$$(u_i, e_k), (e_k, u_j)$

Например, SUBGRAPH ISOMORPHISM NP-труден для вашего класса графиков.

Редукция происходит из гамильтонова цикла на 3-регулярных графах: для 3-регулярного графа построить соответствующий и проверить подграф являющийся замкнутым простым циклом длины, имеет подграф, изоморфный тогда и только тогда, когда имеет гамильтонов цикл.$G$$G' = \{X \cup Y, E'\}$$H'$$2|V|$$G'$$H'$$G$

Эти графы являются графами инцидентности кубических графов, или 2-отрезками 3-регулярных графов. Напишу для падения графа  .$I(G)$$G$

Учитывая график  и целое число  , это NP-полной , чтобы определить , если «s число пересечения не превосходит  (то есть, является ли может быть обращено в плоскости в большинстве  ребер , пересекающих друг друга), даже если  является ограничено быть кубическим. Очевидно, что на число пересечений не влияет добавление дополнительной вершины в середине каждого ребра. (Источник: Hlineny, "число пересечений трудно для кубических графов", Ж. Совмещенный Теор Б.. 96 (4): 455-471; DOI ) .K G K G K $G$$k$$G$$k$$G$$k$$G$

Вполне возможно , что пропускная способность проблема для этих графиков является NP-полной, так как она является NP-полной для деревьев , где каждая вершина имеет степень не более трех. (Источник: Проблема GT40 в Garey и Johnson для общих графов, низкой степени деревьев, Garey, Graham, Джонсон и Кнут, "Результаты минимизации сложности для полосы пропускания", SIAM J. Appl Math.. 34: 477-495; CiteSeer . )

Различные NP-полные задачи графа остаются так далее кубических графов и это приводит к NP-полных задач на соответствующих инцидентности графов , которые являются достаточно естественным. Например, с просьбой , если кубический граф  имеет доминирующее множество размера на большей  эквивалентно с просьбой , если является объединением в большинстве  копий . Кроме того, независимое множество в кубических графике соответствует набору непересекающихся копий в .k I ( G ) k I ( K 1 , 3 ) I ( K 1 , 3 ) I ( G $G$$k$$I(G)$$k$$I(K_{1,3})$$I(K_{1,3})$$I(G)$