TY - JOUR

T1 - Complexity of Computing Convex Subgraphs in Custom Instruction Synthesis

AU - Reddington, Joseph

AU - Atasu, Kubilay

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1109/TVLSI.2011.2173221

DO - 10.1109/TVLSI.2011.2173221

M3 - Article

SN - 1557-9999

SP - 1

EP - 5

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

ER -