2026-07-21T23:33:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8941 2024-03-06T10:42:54Z ddc:004 open_access

Speeding up Dualization in the Fredman-Khachiyan Algorithm B Sedaghat, Nafiseh Stephen, Tamon Chindelevitch, Leonid Monotone boolean functions dualization Fredman-Khachiyan algorithm algorithm engineering metabolic networks The problem of computing the dual of a monotone Boolean function f is a fundamental problem in theoretical computer science with numerous applications. The related problem of duality testing (given two monotone Boolean functions f and g, declare that they are dual or provide a certificate that shows they are not) has a complexity that is not yet known. However, two quasi-polynomial time algorithms for it, often referred to as FK-A and FK-B, were proposed by Fredman and Khachiyan in 1996, with the latter having a better complexity guarantee. These can be naturally used as a subroutine in computing the dual of f. In this paper, we investigate this use of the FK-B algorithm for the computation of the dual of a monotone Boolean function, and present practical improvements to its performance. First, we show how FK-B can be modified to produce multiple certificates (Boolean vectors on which the functions defined by the original f and the current dual g do not provide outputs consistent with duality). Second, we show how the number of redundancy tests - one of the more costly and time-consuming steps of FK-B - can be substantially reduced in this context. Lastly, we describe a simple memoization technique that avoids the solution of multiple identical subproblems. We test our approach on a number of inputs coming from computational biology as well as combinatorics. These modifications provide a substantial speed-up, as much as an order of magnitude, for FK-B dualization relative to a naive implementation. Although other methods may end up being faster in practice, our work paves the way for a principled optimization process for the generation of monotone Boolean functions and their duals from an oracle. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nafiseh Sedaghat and Tamon Stephen and Leonid Chindelevitch 2018 Is Part Of LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2018.6 urn:nbn:de:0030-drops-89413 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode