Поиск древесного разложения в остовном подграфе с ограниченной древесной шириной

Идея FPT (Fixed-Parameter Tractable), параметризированного подхода к оценке сложности задач и алгоритмов, была предложена в конце прошлого века. За последние двадцать лет эта идея получила свое развитие в различных областях компьютерных наук. Среди задач, реализуемых с помощью FPT-алгоритмов, наибольший интерес представляют NP-трудные задачи, поскольку при ограниченном или фиксированном значении параметра теоретически эти задачи могут быть решены за полиномиальное время. Одним из таких параметров является древесная ширина. Древесная ширина и древесные разложения - важные понятия в разработке графовых алгоритмов. Актуальность темы исследования древесной ширины и древесной композиции обоснована возможностью эффективного использования древесных декомпозиций при решении NP-трудных задач (такие алгоритмы строятся на двух этапах – сначала ищется хорошее древесное разложение, а затем на нем решается сама задача) и использованием древесной ширины в качестве параметра для алгоритмов FPT. В отечественной литературе тема древесной ширины и разложения освещена слабо. Результатом моей работы является описание алгоритма нахождения остовного подграфа заданной древесной ширины, определения для него древесной декомпозиции, программная реализация алгоритма на языке Python, работающая за экспоненциальное время относительно величины древесной ширины.