CS Paper Radar

Splitting Planar Necklaces with Few Straight Cuts

Rishi Advani, Abolfazl Asudeh

cs.CG cs.DScs.GT ·submitted 2026-10-20 10:01 UTC · v1

Abstract

In the classical necklace splitting problem, beads of different colors lie on a line, and the goal is to divide them among $k$ agents using as few cuts as possible so that every agent receives the same number of beads of each color. We study the planar analog in which a cut is a full straight line and the objective is minimizing the number of lines: $m$ points colored red and blue must be separated by straight-line cuts into regions that can be allocated to $k$ agents so that each agent receives the same number of points of each color. Projection to a line gives $2(k-1)$ cuts, and $k-1$ are sometimes necessary; we give algorithms, static and dynamic, that provably close part of this gap. We develop several approaches that capitalize on the extra degree of freedom: a ``star'' search that produces solutions with as few as $\lceil \frac{k}{2} \rceil$ cuts and never more than $k$ whenever a fair contiguous circular partition exists, with further guarantees for evenly spaced input, and a general algorithm that produces at most $k + \log_2(k+1) - 2$ cuts in $Θ(m \log k)$ time, built on a one-dimensional necklace splitting subroutine that requires no presorting. We then adapt the general algorithm to a dynamic setting, maintaining exact fairness and the cut bound under arbitrary relocation of points, with expected update time that scales with the total distance moved.

Comment
39 pages, 9 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Endpoint Covering of Axis-Parallel Segments:Bichromatic and Monochromatic One-Center

cs.CG ·2026-09-24 ·Nandana Ghosh, Ankush Acharyya, Rakesh Gupta, Supantha Pandit
similarity 0.70
Abstract · 39

We study exact one-center optimization for axis-parallel segments using axis-parallel squares under endpoint-based coverage, where a segment is \emph{$1$-covered} if the square contains at least one of its endpoints. In the monochromatic problem, we seek a minimum-side-length square that $1$-covers all $n$ input segments. We obtain $O(n\log n)$-time algorithms for both unrestricted and segment-constrained centers. The unrestricted bound matches the known bound implied by the two-representative color-spanning-square problem, whereas the segment-constrained result is new. We also prove matching $Ω(n\log n)$ lower bounds for both center models in the fixed-order algebraic decision-tree model. In the bichromatic problem, an admissible square must fully contain all $m$ blue segments, minimize the number of red segments with an endpoint in its interior, and, subject to this minimum, maximize its side length within a prescribed bounding box. We give deterministic $O(m+n\log^2 n)$-time and $O(m+mn\log n)$-time algorithms for unrestricted and blue-segment-constrained centers, respectively.

0.24

Subexponential Parameterized Approximation for Group-Fair Euclidean $k$-Center

cs.DS ·2026-10-14 ·Rudranarayan Kar, Diya Roy, Abhishek Sahu
similarity 0.64
Abstract

Clustering is a basic tool for grouping data into meaningful classes, but in many applications the resulting clusters must also respect the fairness conditions among different groups. We study this direction for the group-fair Euclidean $k$-center problem in fixed dimension, where the input points are partitioned into disjoint color classes, and every cluster must satisfy given lower and upper bounds on the fraction of each color. We give a separator-based recursive approximation algorithm for the continuous-center setting. The main idea is to first reduce the continuous search space to a finite candidate center set and then use the geometric sphere separators to break the instance into smaller subproblems. Our algorithm gives a bicriteria approximation: the clustering radius is within a factor of $(1+ε)$ of the optimum exactly fair solution, while the fairness bounds are relaxed only by a multiplicative factor. For fixed dimension, number of colors, and approximation parameters, the running time is polynomial in input size and subexponential in $k$. A recent IJCAI-ECAI2026 result gives a $(1+ε)$-approximation for group-fair $k$-center in bounded doubling metrics with running time $(k/ε)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. In the fixed-dimensional Euclidean setting considered here, we improve the dependence on $k$ to subexponential, while allowing continuous centers. The fairness guarantees of the two results are different: the previous work allows an additive fairness violation, whereas our algorithm uses a controlled multiplicative relaxation.

0.07

Bichromatic Line-Centers for Point Pairs

cs.CG ·2026-09-20 ·Jaegun Lee, Youjung Bae, Taehoon Ahn, Sang Won Bae, Hee-Kap Ahn
similarity 0.64
Abstract

We study the \emph{bichromatic line-center problem} for $n$ pairs of points in the plane. A feasible solution assigns one point from each pair to the red set $R$ and the other to the blue set $B$. The goal is to minimize $\max\{w^\circ(R),\,w^\circ(B)\}$, where $w^\circ(X)$ denotes the minimum width of a strip enclosing $X$; the midlines of the corresponding optimal strips define the line-centers of $R$ and $B$. We consider several variants induced by orientational constraints on line-centers and provide efficient algorithms for each. For one line-center, which consists of computing a minimum-width strip that contains at least one point from each pair, we give an $O(n^2)$-time algorithm. For two line-centers, we obtain an $O(n)$-time algorithm when both are horizontal, and $Θ(n\log n)$-time algorithms when the two centers are parallel or when both orientations are prescribed. When exactly one orientation is prescribed, we give an $O(n^2)$-time algorithm. Finally, for the unrestricted case, we present an $O(n^3\log n)$-time algorithm.

0.20

Online Treasure Hunt in Vertex-Permuted Dynamic Rings

cs.DC cs.CC ·2026-09-10 ·Kamran Ayoubi, Bernard Mans, Lata Narayanan
similarity 0.64
Abstract · 21 pages, 3 figures

We study the problem of treasure hunt by a group of $k \geq 1$ agents in vertex-permuted dynamic rings (VP). In this model, the $n$ vertices remain on a ring but are permuted at each time step. We first show that treasure hunt is impossible for any $k \leq n-3$ agents, if there are no restrictions on the sequence of permutations used in the dynamic ring. We then study the $VP(δ)$ setting, in which for every pair $i, j$ of vertices, the edge $(i, j)$ is guaranteed to appear within $δ$ steps. We show that the class $VP(δ)$ is feasible only for $δ\geq \left\lceil \frac{n-1}{2}\right\rceil$. For the one-agent case, we show a tight bound of $Θ(δn)$ on the worst-case search time as well as competitive ratio of any online algorithm for treasure hunt, provided $δ\geq 2n$. We then give an optimal algorithm for $k$ agents, thereby showing that $k$ agents can obtain a speedup of $k$ on the worst-case search time. Finally, in the R-VP setting, in which in every step, the vertices are arranged as a ring according to a random permutation, we show that treasure hunt takes expected $Θ(n)$ steps against an oblivious adversary and $Θ(n \log n)$ steps against an adaptive adversary.

0.34

Maximum Matching-Match: Hardness and Approximation

cs.DS cs.CC ·2026-09-07 ·Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
similarity 0.62
Abstract

In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). Given a graph, a partial vertex coloring, and a multiset of colored sticks, the goal is to complete the coloring and assign the sticks to graph edges so as to maximize the number of satisfied edges. We first prove that \textsc{MaxMMP} is APX-hard by an reduction from \textsc{Max-Cut}. The hardness already holds with two colors, no precolored vertices, and only bichromatic sticks. We then give a simple deterministic $\frac{2}{c(c+1)}$-approximation for completely uncolored instances, improving to $\frac{2}{c(c-1)}$ when all sticks are bichromatic. Next, we obtain a randomized $\frac{1-\frac{1}{e}}{2c}$-approximation for arbitrary instances with $c$ colors by reducing the remaining coloring choices to monotone submodular maximization under a partition matroid. On bipartite graphs, the approximation ratio improves to $\frac{1-\frac{1}{e}}{c}$. For every fixed $c$, we further obtain deterministic $\frac{1}{2c}$ and $\frac{1}{c}$-approximations on general and bipartite graphs, respectively, in time $n^{O(c^2)}$. Finally, for every fixed number of colors, we show that \textsc{MaxMMP} can be solved exactly in time $n^{O(c^2)}$ on trees and on cographs.

0.50

Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs

cs.DM math.CO ·2026-11-04 ·Gautam K. Das, Kamal Santra
theory similarity 0.62
Abstract

A proper conflict-free coloring is a proper coloring in which each nonisolated vertex has a neighbor whose color occurs exactly once in its open neighborhood. We prove that deciding whether the clique number of colors suffices is NP-complete on undirected path graphs, even with a supplied representation by paths in a star. One extra color suffices on every instance in the reduction. We also prove NP-completeness on chordal bipartite graphs for every fixed palette size $k\ge4$. For strongly chordal graphs, reverse simple elimination gives a constructive upper bound of one more than the clique number. We obtain exact polynomial-time algorithms under several conditions on the maximum cliques, including when they induce a connected subtree of a clique tree. For strictly chordal graphs we characterize the optimum and construct an optimal coloring in $O(n+m)$ time, where $n$ and $m$ count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most $s$, we give an exact algorithm in $n^{2^{O(s+1)}}$ time, with no bound on the clique number.

0.12

Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection

cs.DS ·2026-11-05 ·Aditya Anand, Evangelos Kipouridis, Karol Węgrzycki
similarity 0.62
Abstract

The Minimum Bisection problem asks whether an $n$-vertex graph can be split into two halves with at most $k$ edges between them. We give a single exponential time algorithm for minimum bisection, running in time $2^{O(k)}n^{O(1)}$. This improves the previous bound of $2^{O(k\log k)}n^{O(1)}$ due to Cygan, Komosa, Lokshtanov, Pilipczuk, Pilipczuk, Saurabh, and Wahlström (TALG 2021). Our algorithm counts solutions instead of only finding if one exists. We show that our dynamic program can be implemented on top of an unbreakable decomposition using algebraic techniques. Along the way, we compute in time $2^{O(k)}n^{O(1)}$ a tree decomposition with adhesions of size at most $2k$ whose bags are $(3k,k)$-edge-unbreakable inside their own subtrees.

0.19

Minimum Label $k$-Cut on Planar Graphs: Complexity and Color Structure

cs.DS ·2026-10-29 ·Yuanhao Wang, Wei Wang
theory similarity 0.62
Abstract

Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2)$ time, where $N$ is the input size, with no restriction on color frequency or the number of blocks spanned by a color; allowing the maximum monochromatic degree to increase to three already makes the decision version NP-complete. Finally, we prove that the problem remains W[1]-hard parameterized by $k$ on fan graphs, even when every color class is an induced path. These results show that bounding color frequency does not suffice to eliminate parameterized hardness. They also establish a monochromatic-degree boundary for connected colors on cactus graphs and identify complexity barriers to extending this tractable case to outerplanar graphs.

0.16