Paper 2020/1605

$P_4$-free Partition and Cover Numbers

Alexander R. Block and Simina Branzei and Hemanta K. Maji and Himanshi Mehta and Tamalika Mukherjee and Hai H. Nguyen

Abstract

$P_4$-free graphs-- also known as cographs, complement-reducible graphs, or hereditary Dacey graphs--have been well studied in graph theory. We introduce the graph properties of partitioning and covering the edges of a graph with the minimum number of $P_4$-free graphs, namely, the $P_4$-free partition and $P_4$-free cover numbers. We prove that computing these numbers is \npol-complete, even for bipartite graphs. We present bipartite graph constructions where these numbers are at least ${\epsilon N^{1-2\epsilon}}$, for $\epsilon\in\{1/3,1/4,1/5,\dotsc\}$, where $N$ is the number of vertices in each partite set. Finally, we upper bound these numbers for bipartite graphs encoding well-studied Boolean functions from circuit complexity, such as set intersection, set disjointness, and inequality. Our work encodes joint probability distributions and Boolean functions as equivalent bipartite graphs and studies the $P_4$-free partition and cover numbers of these graphs. Leveraging this connection, we present representative applications of these graph properties and their estimates to information-theory and circuit complexity. For applications in information theory, we consider a system where a setup samples from a joint distribution and gives the participants, Alice and Bob, their portion from this joint sample. The objective of Alice and Bob is to non-interactively establish a shared key and extract the left-over entropy from their portion of the samples as independent private randomness. A genie, who observes the joint sample, provides an appropriate assistance to help Alice and Bob with their objective. Lower bounds to the minimum size of the genie's assistance translates into communication and cryptographic lower bounds. We show that (the $\log_2$ of) the $P_4$-free partition number of a graph encoding the joint distribution that the setup uses is equivalent to the size of the genie's assistance. Consequently, the joint distributions corresponding to the bipartite graphs constructed above with high $P_4$-free partition number correspond to joint distributions requiring more assistance from the genie. As a representative application in communication complexity, we study communication complexity of non-deterministic protocols augmented by access to the equality oracle at the output. We show that (the $\log_2$ of) the $P_4$-free cover number of the bipartite graph encoding a Boolean function $f$ is equivalent to the minimum size of the non-deterministic input required by the parties (referred to as the communication complexity of $f$ in this model). Consequently, the functions corresponding to the bipartite graphs with high $P_4$-free cover number have high communication complexity. Furthermore, there are functions with communication complexity close to the \naive protocol where the non-deterministic input reveals the input of a party. Finally, the access to the equality oracle reduces the communication complexity of computing set intersection and disjointness by a constant factor in contrast to the model where parties do not have access to the equality oracle. In the case of computing the inequality function, we show an exponential reduction in the communication complexity.