О сложности некоторых задач, связанных с расширениями графов

Исследуется вычислительная сложность задач, связанных с построением $k$-расширений графов. Доказывается, что задачи распознавания вершинного и реберного $k$-расширения являются NP-полными. Рассматривается сложность распознавания неприводимых, минимальных, точных вершинных и реберных $k$-расширений.
Библиография: 11 названий.