Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More

Abstract

Graph product is a fundamental tool with rich applications in both graph theory and theoretical computer science. It is usually studied in the form $f(G\ast H)$ where $G$ and $H$ are graphs, * is a graph product and $f$ is a graph property. For example, if $f$ is the independence number and * is the disjunctive product, then the product is known to be multiplicative: $f(G\ast H)=f(G)f(H)$. In this paper, we study graph products in the following non-standard form: $f((G\oplus H)\ast J)$ where $G$, $H$ and $J$ are graphs, $\oplus$ and * are two different graph products and $f$ is a graph property. We show that if $f$ is the induced and semi-induced matching number, then for some products $\oplus$ and *, it is subadditive in the sense that $f((G\oplus H)\ast J)\le f(G\ast J)+f(H\ast J)$. Moreover, when $f$ is the poset dimension number, it is almost subadditive. As applications of this result (we only need $J=K_2$ here), we obtain tight hardness of approximation for various problems in discrete mathematics and computer science: bipartite induced and semi-induced matching (a.k.a. maximum expanding sequences), poset dimension, maximum feasible subsystem with 0/1 coefficients, unit-demand min-buying and single-minded pricing, donation center location, boxicity, cubicity, threshold dimension and independent packing.

arXiv commentPreliminary version is published in SODA 2013