Finding one good subgraph and partitioning an entire graph into good subgraphs are fundamentally different tasks. Inspired by the work of Feige and Kilian [Feige and Kilian, JCSS’1998], who proved coloring hardness by modifying a PCP designed for Maximum Clique, we ask whether a graph containing a hidden induced subgraph can be transformed directly into a larger graph that admits a partition into copies of that subgraph, without identifying it.
We give a simple graph-theoretic construction that, given a graph G and a prescribed subgraph size k, produces a target graph Z with this partition guarantee simultaneously for any fixed k-vertex induced subgraph of G. Our construction uses bijections obtained from perfect matchings in a regular bipartite graph of sufficiently large girth.
An immediate application is (partially) recovering N^{1/4−ϵ}-hardness for Graph Coloring under P≠NP through a direct graph reduction from Maximum Clique, without an additional PCP construction. We also reduce Densest-k-Subgraph to Densest-q-Partition, which partitions all vertices into q nonempty parts while maximizing the density of the partition. This yields 2^{(log N)^{1−ϵ}} approximation hardness under Almost-ETH for every fixed ϵ∈(0,1), which can be further extended to other graph problems.
Another key application is (2−ϵ)-hardness for every fixed ϵ>0 under Almost-ETH for Metric Minsum Clustering, even for {1,2}-metrics. This matches the elementary 2-approximation for this class of metrics and improves upon the previous hardness factor of 1.415 [Cohen-Addad et al., SODA’2021].
The applications presented in this paper illustrate the scope of broad applications of our transformation. We expect the technique to find further applications across different areas, beyond those investigated in this paper.