License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.6
URN: urn:nbn:de:0030-drops-89413
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8941/
Go to the corresponding LIPIcs Volume Portal

Sedaghat, Nafiseh ; Stephen, Tamon ; Chindelevitch, Leonid

Speeding up Dualization in the Fredman-Khachiyan Algorithm B

pdf-format:
LIPIcs-SEA-2018-6.pdf (1 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{sedaghat_et_al:LIPIcs:2018:8941,
  author =	{Nafiseh Sedaghat and Tamon Stephen and Leonid Chindelevitch},
  title =	{{Speeding up Dualization in the Fredman-Khachiyan Algorithm B}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8941},
  URN =		{urn:nbn:de:0030-drops-89413},
  doi =		{10.4230/LIPIcs.SEA.2018.6},
  annote =	{Keywords: Monotone boolean functions, dualization, Fredman-Khachiyan algorithm, algorithm engineering, metabolic networks}
}

Keywords: Monotone boolean functions, dualization, Fredman-Khachiyan algorithm, algorithm engineering, metabolic networks
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI