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(GxH) where G and H are graphs, "x" is a graph product and f is a graph property. For example, if f is the independence number and "x" is the disjunctive product, then it is a simple exercise to check that f(GxH)=f(G)f(H).

In this paper, we study graph products in the following non-standard form: f((GxH)\cdot J) where G, H and J are graphs, x and \cdot 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 graph products "x" and "\cdot", it is subadditive in the sense that f((GxH)\cdot J) \leq f(G\cdot J)+f(H\cdot J). Moreover, when function f is the poset dimension number, it is "almost subadditive".

As applications of this result (we only need J=K_2 here), we obtain nearly tight hardness of approximation results for many optimization problems in discrete mathematics and computer science: bipartite induced matching, poset dimension, maximum expanding sequences, maximum feasible subsystem with 0-1 coefficients, profit-maximization pricing (in various settings), boxicity, cubicity, threshold dimension, donation center location, and independent packing.

This work will appear in SODA 2013 (Joint work with Bundit Laekhanukit and Danupon Nanongkai)