Complexity of Computing Convex Subgraphs in Custom Instruction Synthesis
Joseph Reddington, Kubilay Atasu · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · 2011
Synthesis of custom instruction processors from high-level application descriptions involves automated evaluation of data-flow subgraphs as custom instruction candidates. A subgraphSof a graphD, is convex if no two vertices ofSare connected by a path inDthat is not also inS. 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 thanO(|V(D)|Nin+Nout+1) recursive calls, where |V(D)| is the number of vertices inD, andNinandNoutare input and output constraints, respectively. Therefore, whenNinandNoutare constants, the algorithm is of polynomial complexity. Furthermore, a convex subgraphSis 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 enumerate 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.