Maximum Bipartite vs Triangle-Free Subgraph
<|reference_start|>Maximum Bipartite vs Triangle-Free Subgraph: Given a (multi)graph $G$ which contains a bipartite subgraph with $\rho$ edges, what is the largest triangle-free subgraph of $G$ that can be found efficiently? We present an SDP-based algorithm that finds one with at least $0.8823 \rho$ edges, thus improving on the subgraph with $0.878 \rho$ edges obtained by the classic Max-Cut algorithm of Goemans and Williamson. On the other hand, by a reduction from Hastad's 3-bit PCP we show that it is NP-hard to find a triangle-free subgraph with $(25 / 26 + \epsilon) \rho \approx (0.961 + \epsilon) \rho$ edges.   As an application, we classify the Maximum Promise Constraint Satisfaction Problem MaxPCSP($G$,$H$) for all bipartite $G$: Given an input (multi)graph $X$ which admits a $G$-colouring satisfying $\rho$ edges, find an $H$-colouring of $X$ that satisfies $\rho$ edges. This problem is solvable in polynomial time, apart from trivial cases, if $H$ contains a triangle, and is NP-hard otherwise.<|reference_end|>
@article{nakajima2024maximum,
    title={Maximum Bipartite vs. Triangle-Free Subgraph},
    author={Tamio-Vesa Nakajima and Stanislav v{Z}ivn'y},
    journal={arXiv preprint arXiv:2406.20069},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.20069},
    primaryClass={cs.DS cs.CC cs.DM}
}