Loading...
Please wait, while we are loading the content...
Similar Documents
On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems
| Content Provider | Hyper Articles en Ligne (HAL) |
|---|---|
| Author | Knauer, Christian Tiwary, Hans Raj Werner, Daniel |
| Abstract | 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 \emph{Caratheodory set} and a \emph{Helly set} and certain decision versions of the \emph{\hsc\ problem} are \wone-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 \dSum\ 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 \dSum\ into a geometric setting is conceptually much simpler than direct fpt-reductions from purely combinatorial \wone-hard problems (like the clique problem) and has great potential to show (parameterized) hardness and (conditional) lower bounds for many other problems. |
| Ending Page | 660 |
| Page Count | 12 |
| Starting Page | 649 |
| File Format | |
| Volume Number | 9 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | parameterized complexity computational geometry combinatorial geometry ham-sandwich cuts parameterized complexity. info Computer Science [cs] Computational Complexity [cs.CC] Data Structures and Algorithms [cs.DS] |
| Content Type | Text |
| Resource Type | Article |
