Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more

Parinya Chalermsook*, Bundit Laekhanukit, Danupon Nanongkai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

37 Citations (Scopus)


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 * 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 * H) = f(G)f(H). In this paper, we study graph products in the following non-standard form: f((G⊕H)*J) where G, H and J are graphs, ⊕ 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 ⊕ and *, it is subadditive in the sense that f((G⊕H) * J) ≤ f(G * J) + f(H * J). Moreover, when f is the poset dimension number, it is almost subadditive. As applications of this result (we only need J = K2 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.

Original languageEnglish
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Number of pages20
Publication statusPublished - 2013
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States
Duration: 6 Jan 20138 Jan 2013
Conference number: 24


ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
Country/TerritoryUnited States
CityNew Orleans


Dive into the research topics of 'Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more'. Together they form a unique fingerprint.

Cite this