О сложности задачи размещения на линии с ограничениями на минимальные расстояния

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