2026-08-16T23:24:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3051 2024-03-06T10:33:48Z ddc:004 open_access

On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems Knauer, Christian Tiwary, Hans Raj Werner, Daniel computational geometry combinatorial geometry ham-sandwich cuts parameterized complexity. We study several canonical decision problems arising from some well-known theorems from combinatorial geometry. Among others, we show that computing the minimum size of a Caratheodory set and a Helly set and certain decision versions of the hs cut problem are W[1]-hard (and NP-hard) if the dimension is part of the input. This is done by fpt-reductions (which are actually ptime-reductions) from the d-Sum problem. Our reductions also imply that the problems we consider cannot be solved in time n^{o(d)} (where n is the size of the input), unless the Exponential-Time Hypothesis (ETH) is false. The technique of embedding d-Sum into a geometric setting is conceptually much simpler than direct fpt-reductions from purely combinatorial W[1]-hard problems (like the clique problem) and has great potential to show (parameterized) hardness and (conditional) lower bounds for many other problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Knauer and Hans Raj Tiwary and Daniel Werner 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.649 urn:nbn:de:0030-drops-30514 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.649 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode