построение ациклического графа кусочно

Question

Я хотел бы построить ациклический граф.

Мне нужно построить это снизу вверх, потому что я могу только построить только подграф с ограниченным количеством узлов за раз.Я также могу прикрепить корень такого подграфа куда угодно.

Например, давайте предположим, что я хочу построить следующий граф (g).Края ориентированы и всегда направлены вниз.Также допускается использование нескольких ребер, поскольку это очевидно между G и I (я не думаю, что это сильно повлияет на алгоритм).

           A 
         / | \
        B  |  D 
        | /   | \  
  g =   C     E  F 
              | /
              G
             / \\
            H   I

Давайте предположим, что я могу создавать не более 5 узлов одновременно.График может быть построен в 3 этапа.

Сначала создайте подграф (g1) с 3 узлами:

          G
  g1 =   / \\
        H   I

После этого мы можем добавить другой подграф (g2) с g1, прикрепленным внизу

          D           D
          | \         | \
          E  F        E  F
 g2 =     | /    =    | /
          g1          G
                     / \\
                    H   I           

Наконец, мы можем построить график (g):

           A               A 
         / | \           / | \
        B  |  g2        B  |  D 
        | /             | /   | \  
 g =    C          =    C     E  F 
                              | /
                              G
                             / \\
                            H   I           

Надеемся, проблема ясна из примера.Я пытаюсь составить алгоритм, который для данного DAG и максимального размера идентифицирует такие части или приходит к выводу, что решения не существует.Например, граф (g) не может быть разделен, если максимальный размер равен 2.

Очевидно, что это будет тривиально для решения в дереве.

Существует ли алгоритм для этого?У этой или подобной проблемы есть имя?