On the complexity of design tasks for Digital Microfluidic Biochips

Digital Microfluidic Biochips (DMFBs) is an emerging technology aiming at the automatic processing of biological assays. Experiments are conducted by routing droplets of liquids on a grid. Determining a routing is the first step in the design process. A particular routing is carried out by actuating the cells of the DMFB grid in a certain manner. These actuations are controlled by microcontrollers having a limited number of output pins. Thus, it is usually not possible to control each cell separately, but multiple cells have to share a common control pin leading to the pin assignment problem. In recent years, a wide range of heuristic as well as exact approaches has been proposed to solve these problems. While the N P-completeness of routing and pM assignment has already been conjectured in the literature, we present the first actual proofs. Thus, the use of general-purpose approaches like SAT solvers is indeed justified. We additionally prove the N P-completeness for variants of the routing problem.