Complexity of Computing Convex Subgraphs in Custom Instruction Synthesis

Synthesis of custom instruction processors from high-level application descriptions involves automated evaluation of data-flow subgraphs as custom instruction candidates. A subgraph $S$ of a graph $D$ , is convex if no two vertices of $S$ are connected by a path in $D$ that is not also in $S$. An algorithm for enumerating all convex subgraphs of a directed acyclic graph (DAG) under input, output, and forbidden vertex constraints was given by Pozzi, Atasu, and Ienne. We show that this algorithm makes no more than $O(vert V(D)vert^{N_{rm in}+N_{rm out}+1})$ recursive calls, where $vert V(D)vert$ is the number of vertices in $D$, and $N_{rm in}$ and $N_{rm out}$ are input and output constraints, respectively. Therefore, when $N_{rm in}$ and $N_{rm out}$ are constants, the algorithm is of polynomial complexity. Furthermore, a convex subgraph $S$ is a maximal convex subgraph if it is not a proper subgraph of some other convex subgraph, assuming that both are valid under forbidden vertex constraints. The largest maximal convex subgraph is called the maximum convex subgraph. There exist popular algorithms that enume- - rate maximal convex subgraphs, which all have exponential worst-case time complexity. This work shows that although no polynomial-time maximal convex subgraph enumeration algorithm can exist, the related maximum convex subgraph problem can be solved in polynomial time.