Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs

Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai

The study of graph products is a major research topic and typically concerns the term $f(G\ast H)$, e.g., to show that $f(G\ast H)=f(G)f(H)$. In this paper, we study graph products in a no…