Publications in Scientific Journals:

R. Ganian, M. Kronegger, A. Pfandler, A. Popa:
"Parameterized Complexity of Asynchronous Border Minimization";
Algorithmica, 81 (2019), 1; 201 - 223.

English abstract:
Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). The common task of these two problems is to create so-called probe sequences (essentially a string) in a microarray. Here, the goal of the former problem is to determine an assignment of each probe sequence to a unique cell of the array and afterwards to construct the sequences at their respective cells while minimizing the border length of the probes. In contrast, for the latter problem the assignment of the probes to the cells is already given. In this paper we investigate the parameterized complexity of the natural exhaustive variants of BMP and P-BMP, termed BMP𝑒 and P-BMP𝑒 respectively, under several natural parameters. We show that BMP𝑒 and P-BMP^{𝑒} are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (ℓ) and the number of rows of the microarray (r); and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMP𝑒 is in FPT when parameterized by c and ℓ. We complement our tractability results with a number of corresponding hardness results.

Parameterized complexity; Fixed-parameter tractability; NP-hard problem; Microarrays

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Related Projects:
Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen

Project Head Stefan Szeider:
Exploiting New Types of Structure for Fixed Parameter Tractability

Project Head Stefan Woltran:

Created from the Publication Database of the Vienna University of Technology.