ON THE SIZE OF A MINIMAL VERTEX COVER IN A RANDOM SUBGRAPH OF THE n-CUBE
Eduard Toman, Martin Staněk · 2009
We describe and analyze a construction of a vertex cover (consisting of subcubes) in a random subgraph of the n-cube. The main idea of the construction is to select subcubes with minimal intersection into the vertex cover. We estimate the upper bound of such a vertex cover. Our analysis gives a theoretical justification for a heuristic that minimizes the disjunctive normal form of a random Boolean function by selecting conjunctions according to the strategy of minimal intersections.