2014/08/04 by Parinya Chalermsook, Chalermsook, Parinya, Bundit Laekhanukit +3 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1408.0828
arxiv created 2014/08/04 · openalex publication_date 2014/08/04 · arxiv updated 2014/08/06 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
The study of graph products is a major research topic and typically concerns the term f(G*H), e.g., to show that f(G*H)=f(G)f(H). In this paper, we study graph products in a non-standard form f(R[G*H] where R is a "reduction", a transformation of any graph into an instance of an intended optimization problem. We resolve some open problems as applications. (1) A tight n1-ε-approximation hardness for the minimum consistent deterministic finite automaton (DFA) problem, where n is the sample size. Due to Board and Pitt [Theoretical Computer Science 1992], this implies the hardness of properly learning DFAs assuming NP≠ RP (the weakest possible assumption). (2) A tight n1/2-ε hardness for the edge-disjoint paths (EDP) problem on directed acyclic graphs (DAGs), where n denotes the number of vertices. (3) A tight hardness of packing vertex-disjoint k-cycles for large k. (4) An alternative (and perhaps simpler) proof for the hardness of properly learning DNF, CNF and intersection of halfspaces [Alekhnovich et al., FOCS 2004 and J. Comput.Syst.Sci. 2008].