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

Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai

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 g…