TY - GEN

T1 - On the readability of monotone boolean formulae

AU - Elbassioni, Khaled

AU - Makino, Kazuhisa

AU - Rauf, Imran

PY - 2009

Y1 - 2009

N2 - Golumbic et al. [Discrete Applied Mathematics 154(2006) 1465-1477] defined the readability of a monotone Boolean function f to be the minimum integer k such that there exists an ∧-∨-formula equivalent to f in which each variable appears at most k times. They asked whether there exists a polynomial-time algorithm, which given a monotone Boolean function f, in CNF or DNF form, checks whether f is a read-k function, for a fixed k. In this paper, we partially answer this question already for k=2 by showing that it is NP-hard to decide if a given monotone formula represents a read-twice function. It follows also from our reduction that it is NP-hard to approximate the readability of a given monotone Boolean function f:{0,1}n→{0,1} within a factor of . We also give tight sublinear upper bounds on the readability of a monotone Boolean function given in CNF (or DNF) form, parameterized by the number of terms in the CNF and the maximum size in each term, or more generally the maximum number of variables in the intersection of any constant number of terms. When the variables of the DNF can be ordered so that each term consists of a set of consecutive variables, we give much tighter polylogarithmic bounds on the readability.

AB - Golumbic et al. [Discrete Applied Mathematics 154(2006) 1465-1477] defined the readability of a monotone Boolean function f to be the minimum integer k such that there exists an ∧-∨-formula equivalent to f in which each variable appears at most k times. They asked whether there exists a polynomial-time algorithm, which given a monotone Boolean function f, in CNF or DNF form, checks whether f is a read-k function, for a fixed k. In this paper, we partially answer this question already for k=2 by showing that it is NP-hard to decide if a given monotone formula represents a read-twice function. It follows also from our reduction that it is NP-hard to approximate the readability of a given monotone Boolean function f:{0,1}n→{0,1} within a factor of . We also give tight sublinear upper bounds on the readability of a monotone Boolean function given in CNF (or DNF) form, parameterized by the number of terms in the CNF and the maximum size in each term, or more generally the maximum number of variables in the intersection of any constant number of terms. When the variables of the DNF can be ordered so that each term consists of a set of consecutive variables, we give much tighter polylogarithmic bounds on the readability.

UR - http://www.scopus.com/inward/record.url?scp=76249084225&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02882-3_49

DO - 10.1007/978-3-642-02882-3_49

M3 - Conference contribution

AN - SCOPUS:76249084225

SN - 3642028810

SN - 9783642028816

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 496

EP - 505

BT - Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings

T2 - 15th Annual International Conference on Computing and Combinatorics, COCOON 2009

Y2 - 13 July 2009 through 15 July 2009

ER -