2026-08-17T06:36:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23498 2025-06-30T07:23:11Z ddc:004 open_access

Maximum Bipartite vs. Triangle-Free Subgraph Nakajima, Tamio-Vesa Živný, Stanislav approximation promise constraint satisfaction triangle-free subgraphs Given a (multi)graph G which contains a bipartite subgraph with ρ 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 ρ edges, thus improving on the subgraph with 0.878 ρ edges obtained by the classic Max-Cut algorithm of Goemans and Williamson. On the other hand, by a reduction from Håstad’s 3-bit PCP we show that it is NP-hard to find a triangle-free subgraph with (25 / 26 + ε) ρ ≈ (0.961 + ε) ρ edges. As an application, we classify the Maximum Promise Constraint Satisfaction Problem, denoted byMaxPCSP(G, H), for all bipartite G: Given an input (multi)graph X which admits a G-colouring satisfying ρ edges, find an H-colouring of X that satisfies ρ edges. This problem is solvable in polynomial time, apart from trivial cases, if H contains a triangle, and is NP-hard otherwise. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tamio-Vesa Nakajima and Stanislav Živný 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.121 urn:nbn:de:0030-drops-234987 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.121 eng https://creativecommons.org/licenses/by/4.0/legalcode