2026-10-01T07:51:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25568 2026-09-23T23:44:12Z ddc:004 open_access

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More Stoian, Mihail doubling constant parametrization weighted problems traveling salesman weighted max-cut edge-weighted k-clique Despite much research, hard weighted problems still resist super-polynomial improvements over their textbook solution. On the other hand, the unweighted versions of these problems have recently witnessed the sought-after speedups. Currently, the only way to repurpose the algorithm of the unweighted version for the weighted version is to employ a polynomial embedding of the input weights. This, however, introduces a pseudo-polynomial factor into the running time, which becomes impractical for arbitrarily weighted instances. In this paper, we introduce a new way to repurpose the algorithm of the unweighted problem. Specifically, we show that the time complexity of several well-known NP-hard problems operating over the (min, +) and (max, +) semirings, such as TSP, Weighted Max-Cut, and Edge-Weighted k-Clique, is proportional to that of their unweighted versions when the set of input weights has small doubling. We achieve this by a meta-algorithm that converts the input weights into polynomially bounded integers using the recent constructive Freiman’s theorem by Randolph and Węgrzycki [ESA 2024] before applying the polynomial embedding. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mihail Stoian 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.79 urn:nbn:de:0030-drops-255680 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.79 eng https://creativecommons.org/licenses/by/4.0/legalcode