The famous Ham-Sandwich theorem states that any d point sets in ℝ^d can be simultaneously bisected by a single hyperplane. The α-Ham-Sandwich theorem gives a sufficient condition for the existence of biased cuts, i.e., hyperplanes that do not cut off half but some prescribed fraction of each point set. We give two new proofs for this theorem. The first proof is completely combinatorial and highlights a strong connection between the α-Ham-Sandwich theorem and Unique Sink Orientations of grids. The second proof uses point-hyperplane duality and the Poincaré-Miranda theorem and allows us to generalize the result to and beyond oriented matroids. For this we introduce a new concept of rainbow arrangements, generalizing colored pseudo-hyperplane arrangements. Along the way, we also show that the realizability problem for rainbow arrangements is ∃ℝ-complete, which also implies that the realizability problem for grid Unique Sink Orientations is ∃ℝ-complete.

Abstract It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the $$\textsf{PPA}$$ -completeness of the Ham Sandwich problem [Filos-Ratsikas and Goldberg, STOC’19]. Recently, a variant of the Ham Sandwich problem called $$\alpha $$ -Ham Sandwich has been studied, in which the point sets are guaranteed to be well-separated [Steiger and Zhao, DCG’10]. The complexity of this search problem remains unknown, but it is known to lie in the complexity class $$\textsf{UEOPL}$$ [Chiu, Choudhary and Mulzer, ICALP’20]. We define the analogue of this well-separation condition in the necklace splitting problem — a necklace is n - separable , if every subset A of the n types of jewels can be separated from the types $$[n]\setminus A$$ by at most n separator points. Since this version of necklace splitting reduces to $$\alpha $$ -Ham Sandwich in a solution-preserving way it follows that instances of this version always have unique solutions. We furthermore provide two FPT algorithms: The first FPT algorithm solves 2-Thief-Necklace-Splitting on $$(n-1+\ell )$$ -separable necklaces with n types of jewels and m total jewels in time $$2^{O(\ell \log \ell )}+O(m^2)$$ . In particular, this shows that 2-Thief-Necklace-Splitting is polynomial-time solvable on n -separable necklaces. Thus, attempts to show hardness of $$\alpha $$ -Ham Sandwich through reduction from the 2-Thief-Necklace-Splitting problem cannot work. The second FPT algorithm tests $$(n-1+\ell )$$ -separability of a given necklace with n types of jewels in time $$2^{O(\ell ^2)}\cdot n^4$$ . In particular, n -separability can thus be tested in polynomial time, even though testing well-separation of point sets is $$\textsf{coNP}$$ -complete [Bergold et al., SWAT’22].

We prove that an $\varepsilon$-approximate fixpoint of a map $f:[0,1]^{d} \rightarrow[0,1]^{d}$ can be found with $\mathcal{O}\left(d^{2}\left(\log \frac{1}{\varepsilon}+\log \frac{1}{1-\lambda}\right)\right)$ queries to f if f is $\lambda$-contracting with respect to an $\ell_{p}$-metric for some $p \in[1, \infty) \cup\{\infty\}$. This generalizes a recent result of Chen, Li, and Yannakakis [STOC 2024] from the $\ell_{\infty}$-case to all $\ell_{p}$ metrics. Previously, all query upper bounds for $p \in[1, \infty) \backslash\{2\}$ were either exponential in $d, \log \frac{1}{\varepsilon}$, or $\log \frac{1}{1-\lambda}$. Chen, Li, and Yannakakis also show how to ensure that all queries to f lie on a discrete grid of limited granularity in the $\ell_{\infty}$-case. We provide such a rounding for the $\ell_{1}$-case, placing an appropriately defined version of the $\ell_{1}$-case in FPdt. To prove our results, we introduce the notion of $\ell_{p}$-halfspaces and generalize the classical centerpoint theorem from discrete geometry: for any $p \in[1, \infty) \cup\{\infty\}$ and any mass distribution (or point set), we prove that there exists a centerpoint c such that every $\ell_{p}$-halfspace defined by c and a normal vector contains at least a $\frac{1}{d+1}$-fraction of the mass (or points).

The Necklace Splitting problem is a classical problem in combinatorics that has been intensively studied both from a combinatorial and a computational point of view. It is well-known that the Necklace Splitting problem reduces to the discrete Ham Sandwich problem. This reduction was crucial in the proof of PPA-completeness of the Ham Sandwich problem. Recently, Borzechowski, Schnider and Weber [ISAAC'23] introduced a variant of Necklace Splitting that similarly reduces to the $α$-Ham Sandwich problem, which lies in the complexity class UEOPL but is not known to be complete. To make this reduction work, the input necklace is guaranteed to be n-separable. They showed that these necklaces can be fairly split in polynomial time and thus this subproblem cannot be used to prove UEOPL-hardness for $α$-Ham Sandwich. We consider the more general unfair necklace splitting problem on n-separable necklaces, i.e., the problem of splitting these necklaces such that each thief gets a desired fraction of each type of jewels. This more general problem is the natural necklace-splitting-type version of $α$-Ham Sandwich, and its complexity status is one of the main open questions posed by Borzechowski, Schnider and Weber. We show that the unfair splitting problem is also polynomial-time solvable, and can thus also not be used to show UEOPL-hardness for $α$-Ham Sandwich.

Abstract MaxCut is a classical $$\textsf{NP}$$ NP -complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdös bound states that any connected graph on n vertices with m edges contains a cut of size at least $$\frac{m}{2}+\frac{n-1}{4}$$ m 2 + n - 1 4 . Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdös bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., $$f(k)\cdot O(m)$$ f ( k ) · O ( m ) . We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdös bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of weight at least $$\frac{w(G)}{2}+\frac{w_{MSF}(G)}{4}$$ w ( G ) 2 + w MSF ( G ) 4 , where w(G) denotes the total weight of G, and $$w_{MSF}(G)$$ w MSF ( G ) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., $$f(k)\cdot O(m+n)$$ f ( k ) · O ( m + n ) .

Schaefer's dichotomy theorem [Schaefer, STOC'78] states that a boolean constraint satisfaction problem (CSP) is polynomial-time solvable if one of six given conditions holds for every type of constraint allowed in its instances. Otherwise, it is NP-complete. In this paper, we analyze boolean CSPs in terms of their topological complexity, instead of their computational complexity. We attach a natural topological space to the set of solutions of a boolean CSP and introduce the notion of projection-universality. We prove that a boolean CSP is projection-universal if and only if it is categorized as NP-complete by Schaefer's dichotomy theorem, showing that the dichotomy translates exactly from computational to topological complexity. We show a similar dichotomy for SAT variants and homotopy-universality.

We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sink orientation (USO), and a variant of the $α$-Ham Sandwich problem. For all three settings, we show that "two choices are enough", meaning that the general non-binary version of the problem can be reduced in polynomial time to the binary version. This specifically means that generalized P-LCPs are equivalent to P-LCPs, and grid USOs are equivalent to cube USOs. These results are obtained by showing that both the P-LCP and our $α$-Ham Sandwich variant are equivalent to a new problem we introduce, P-Lin-Bellman. This problem can be seen as a new tool for formulating problems as P-LCPs.

Abstract Let P be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in P. We say two points $$a,b\in P$$ a , b ∈ P can see each other if the line segment $${\text {seg}} (a,b)$$ seg ( a , b ) is contained in P. We denote by V(P) the family of all minimum guard placements. The Hausdorff distance makes V(P) a metric space and thus a topological space. We show homotopy-universality, that is, for every semi-algebraic set S there is a polygon P such that V(P) is homotopy equivalent to S. Furthermore, for various concrete topological spaces T, we describe instances I of the art gallery problem such that V(I) is homeomorphic to T.

It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the PPA-completeness of the Ham Sandwich problem [Filos-Ratsikas and Goldberg, STOC'19]. Recently, a variant of the Ham Sandwich problem called $α$-Ham Sandwich has been studied, in which the point sets are guaranteed to be well-separated [Steiger and Zhao, DCG'10]. The complexity of this search problem remains unknown, but it is known to lie in the complexity class UEOPL [Chiu, Choudhary and Mulzer, ICALP'20]. We define the analogue of this well-separability condition in the necklace splitting problem -- a necklace is $n$-separable, if every subset $A$ of the $n$ types of jewels can be separated from the types $[n]\setminus A$ by at most $n$ separator points. By the reduction to the Ham Sandwich problem it follows that this version of necklace splitting has a unique solution. We furthermore provide two FPT algorithms: The first FPT algorithm solves 2-Thief-Necklace-Splitting on $(n-1+\ell)$-separable necklaces with $n$ types of jewels and $m$ total jewels in time $2^{O(\ell\log\ell)}+m^2$. In particular, this shows that 2-Thief-Necklace-Splitting is polynomial-time solvable on $n$-separable necklaces. Thus, attempts to show hardness of $α$-Ham Sandwich through reduction from the 2-Thief-Necklace-Splitting problem cannot work. The second FPT algorithm tests $(n-1+\ell)$-separability of a given necklace with $n$ types of jewels in time $2^{O(\ell^2)}\cdot n^4$. In particular, $n$-separability can thus be tested in polynomial time, even though testing well-separation of point sets is coNP-complete [Bergold et al., SWAT'22].

We propose Slim Graph: the first programming model and framework for practical lossy graph compression that facilitates high-performance approximate graph processing, storage, and analytics. Slim Graph enables the developer to express numerous compression schemes using small and programmable compression kernels that can access and modify local parts of input graphs. Such kernels are executed in parallel by the underlying engine, isolating developers from complexities of parallel programming. Our kernels implement novel graph compression schemes that preserve numerous graph properties, for example connected components, minimum spanning trees, or graph spectra. Finally, Slim Graph uses statistical divergences and other metrics to analyze the accuracy of lossy graph compression. We illustrate both theoretically and empirically that Slim Graph accelerates numerous graph algorithms, reduces storage used by graph datasets, and ensures high accuracy of results. Slim Graph may become the common ground for developing, executing, and analyzing emerging lossy graph compression schemes.