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

Изучается вычислительная сложность и сложность аппроксимации задачи о наименьшем бикликовом покрытии вершин графа и задачи о наименьшем бикликовом покрытии ребер графа. Известно, что задачи $NP$-полны в классе двудольных графов. Установлено, что первая задача решается за полиномиальное время в классе $S_{1,2,3}$-свободных двудольных графов, где $S_{1,2,3}$ — граф с вершинами $a,~b,~c,~d,~e,~f,~g$ и ребрами $ab,~bc,~cd,~fe,~ed,~gd.$ Показано, что первая задача в классе двудольных графов не аппроксимируется за полиномиальное время с гарантированной оценкой точности $k\ln n,$ где $0<k<0.25$ — константа, а $n$ — количество вершин в заданном графе (в предположении $P\ne NP$) и решается за полиномиальное время с гарантированной оценкой точности $H_n,$ где $H_n$ — $n$-я частичная сумма гармонического ряда. Доказана $NP$-полнота задачи о наименьшем бикликовом покрытии ребер графа в классе $(K_{3,4},K_{3,4}-e)$-свободных двудольных графов со степенью вершин не более 7.