In the CAPACITATED d-HlTTING Set problem input is a universe U equipped with a capacity function cap : U → ℕ, and a collection A of subsets of U, each of size at most d. The task is to find a minimum size subset S of U and an assignment φ : A → S such that, for every set A ∈ A we have φ (Α ) ∈ A and for every x ∈ U we have |φ-1(χ)| ≤ cap(x ). Here φ-1(χ) is the collection of sets in A mapped to x by φ. Such a set S is called a capacitated hitting set. When d = 2 the problem is known under the name CAPACITATED VERTEX COVER. In Weighted Capacitated d-HlTTING Set each element of U has a positive integer weight and the goal is to find a capacitated hitting set of minimum weight.

We introduce and study the k -center clustering problem with set outliers, a natural and practical generalization of the classical k -center clustering with outliers. Instead of removing individual data points, our model allows discarding up to z subsets from a given family of candidate outlier sets H. More formally, given a metric space (P,dist), where P is a set of elements and dist a distance metric, a family of sets H ⊆ 2 P , and parameters k, z, the goal is to compute a set of k centers C ⊆ P and a family of z sets H ⊆ H such that C∩(⋃ h ∈ H h)=∅ to minimize max p ∈ P∖(⋃ h ∈ H h) min c ∈ C dist (p,c) (clustering cost). This abstraction captures structured noise common in database applications, such as faulty data sources or corrupted records in data integration and sensor systems. We present the first approximation algorithms for this problem in both general and geometric settings. Our methods provide tri-criteria approximations: selecting up to 2k centers and 2f z outlier sets (where f is the maximum number of sets that a point belongs to), while achieving constant-factor approximation in clustering cost. In geometric settings, we leverage range and BBD trees to achieve near-linear time algorithms. In many real applications f=1. In this case we further improve the running time of our algorithms by constructing small coresets. We also provide a hardness result for the general problem showing that it is unlikely to get any sublinear approximation on the clustering cost selecting less than f • z outlier sets. We demonstrate that this model naturally captures relational clustering with outliers. We define and study two new formulations: one where outliers are result tuples in a join, and another where outliers are input tuples whose removal affects the join output. We provide approximation algorithms for both, establishing a tight connection between robust clustering and relational query evaluation.

Efficient query evaluation in databases and solving constraint satisfaction problems (CSPs) are crucial for improving performance in many real-world applications, from large-scale data management to decision-making systems. These problems naturally admit hypergraph representations, and are efficiently solvable using hypertree decomposition techniques, when the decomposition width is small. However, these techniques require finding small-width decompositions efficiently. This remains a significant challenge despite research from both the database and theory communities. In this work we present Ralph (Randomized Approximation using Linear Programming for Hypertree-Decompositions), a fast algorithm to compute low width fractional and generalized hypertree decompositions for input hypergraphs, as well as lower bounds for these widths. We build on the recent breakthrough by Korchemna et al. [FOCS 2024], which introduced the first polynomial time approximation algorithm for fractional (generalized) hypertree width. Our approach combines this theoretical advancement with practical heuristic improvements utilizing (mixed-integer) linear programs. Along the way, we present new algorithms with strong theoretical guarantees. Through empirical evaluation on the nearly 3700 instances of HyperBench, a well established benchmark suite for hypertree decompositions, we find near optimal decompositions for all previously solved instances and low width decompositions for all 500 previously unsolved instances, effectively pushing state-of-the-art.

We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input n-vertex m-edge hypergraph$H$of fractional hypertree width at most$\omega$, runs in polynomial time and produces a tree decomposition of$H$of fractional hypertree width$\mathcal{O}(\omega\log n\log\omega)$, i.e., it is an$\mathcal{O}(\log n\log\omega)$-approximation algorithm. As an immediate corollary this yields poly-nomial time$\mathcal{O}(\log^{2}n\log\omega)$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when$\omega$is considered a constant. For hypergraphs where every pair of hyperedges have at most$\eta$vertices in common, the al-gorithm outputs a hypertree decomposition with fractional hypertree width$\mathcal{O}(\eta\omega^{2}\log\omega)$and generalized hypertree width$\mathcal{O}(\eta\omega^{2}\log\omega(\log\eta+\text{log}\omega))$. This ratio is comparable with the recent algorithm of Lanzinger and Razgon [STACS 2024], which produces a hypertree decomposition with generalized hypertree width${\mathcal{O}}(\omega^{2}(\omega+\eta))$, but uses time (at least) exponential in$\eta$and$\omega$. The second algorithm runs in time$n^{\omega}m^{\mathcal{O}(1)}$and pro-duces a tree decomposition of$H$of fractional hypertree width$\mathcal{O}(\omega{\mathrm{l}}\text{og}^{2}\omega)$. This significantly improves over the$(n+m)^{\mathcal{O}(\omega^{3})}$time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hyper-tree width$\mathcal{O}(\omega^{3})$, both in terms of running time and the approximation ratio. Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger's Theorem for clique separators in graphs: For every graph$G$, vertex sets$A$and$B$, family$\mathcal{F}$of cliques in$G$, and positive rational$f$, either there exists a sub-family of$\mathcal{O}(f \cdot {\mathrm{l}}\text{og}^{2}n)$cliques in$\mathcal{F}$whose union separates$A$from$B$, or there exist$f\cdot\log\vert \mathcal{F}\vert$paths from$A$to$B$such that no clique in$\mathcal{F}$intersects more than$\log\vert \mathcal{F}\vert$paths.

In the Min $k$-Cut problem, the input consists of an edge weighted graph $G$ and an integer $k$, and the task is to partition the vertex set into $k$ nonempty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$ is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta, Lee, and Li [ Proceedings of the 29 th Annual ACM-SIAM Symposium on Discrete Algorithms, A. Czumaj, ed., SIAM, Philadelphia, 2018, pp. 2821–2837] initiated the study of FPT-approximation for the Min $k$-Cut problem and gave a 1.9997-approximation algorithm running in time $2^{\mathcal{O}(k^6)}n^{\mathcal{O}(1)}$. Later, the same set of authors [ Proceedings of the 59 th IEEE Annual Symposium on Foundations of Computer Science, M. Thorup, ed., 2018, pp. 113–123] designed a $(1 +\epsilon)$-approximation algorithm that runs in time $(k/\epsilon)^{\mathcal{O}(k)}n^{k+\mathcal{O}(1)}$ and a 1.81-approximation algorithm running in time $2^{\mathcal{O}(k^2)}n^{\mathcal{O}(1)}$. More, recently, Kawarabayashi and Lin [ Proceedings of the 31 st ACM-SIAM Symposium on Discrete Algorithms, S. Chawla, ed., SIAM, Philadelphia, 2020, pp. 990–999] gave a $(5/3 + \epsilon)$-approximation for Min $k$-Cut running in time $2^{\mathcal{O}(k^2 \log k)}n^{\mathcal{O}(1)}$. In this paper, we give a parameterized approximation algorithm with best possible approximation guarantee and best possible running time dependence on said guarantee (up to the exponential time hypothesis and constants in the exponent). In particular, for every $\epsilon > 0$, the algorithm obtains a $(1 +\epsilon)$-approximate solution in time $(k/\epsilon)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. The main ingredients of our algorithm are a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time $s^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ on unweighted (multi-) graphs. Here, $s$ denotes the number of edges in a minimum $k$-cut. The latter two are of independent interest.

In the Minimum Bisection problem input is a graph G and the goal is to partition the vertex set into two parts A and B, such that ||A|-|B|| ≤ 1 and the number k of edges between A and B is minimized. The problem is known to be NP-hard, and assuming the Unique Games Conjecture even NP-hard to approximate within a constant factor [Khot and Vishnoi, J.ACM'15]. On the other hand, a 𝒪(log n)-approximation algorithm [Räcke, STOC'08] and a parameterized algorithm [Cygan et al., ACM Transactions on Algorithms'20] running in time k^𝒪(k) n^𝒪(1) is known. The Minimum Bisection problem can be viewed as a clustering problem where edges represent similarity and the task is to partition the vertices into two equally sized clusters while minimizing the number of pairs of similar objects that end up in different clusters. Motivated by a number of egregious examples of unfair bias in AI systems, many fundamental clustering problems have been revisited and re-formulated to incorporate fairness constraints. In this paper we initiate the study of the Minimum Bisection problem with fairness constraints. Here the input is a graph G, positive integers c and k, a function χ:V(G) → {1, …, c} that assigns a color χ(v) to each vertex v in G, and c integers r_1,r_2,⋯,r_c. The goal is to partition the vertex set of G into two almost-equal sized parts A and B with at most k edges between them, such that for each color i ∈ {1, …, c}, A has exactly r_i vertices of color i. Each color class corresponds to a group which we require the partition (A, B) to treat fairly, and the constraints that A has exactly r_i vertices of color i can be used to encode that no group is over- or under-represented in either of the two clusters. We first show that introducing fairness constraints appears to make the Minimum Bisection problem qualitatively harder. Specifically we show that unless FPT=W[1] the problem admits no f(c)n^𝒪(1) time algorithm even when k = 0. On the other hand, our main technical contribution shows that is that this hardness result is simply a consequence of the very strict requirement that each color class i has exactly r_i vertices in A. In particular we give an f(k,c,ε)n^𝒪(1) time algorithm that finds a balanced partition (A, B) with at most k edges between them, such that for each color i ∈ [c], there are at most (1±ε)r_i vertices of color i in A. Our approximation algorithm is best viewed as a proof of concept that the technique introduced by [Lampis, ICALP'18] for obtaining FPT-approximation algorithms for problems of bounded tree-width or clique-width can be efficiently exploited even on graphs of unbounded width. The key insight is that the technique of Lampis is applicable on tree decompositions with unbreakable bags (as introduced in [Cygan et al., SIAM Journal on Computing'14]). An important ingredient of our approximation scheme is a combinatorial result that may be of independent interest, namely that for every k, every graph G admits a tree decomposition with adhesions of size at most 𝒪(k), unbreakable bags, and logarithmic depth.

Given an edge-weighted graph, how many minimum $k$-cuts can it have? This is a fundamental question in the intersection of algorithms, extremal combinatorics, and graph theory. It is particularly interesting in that the best known bounds are algorithmic: they stem from algorithms that compute the minimum $k$-cut. In 1994, Karger and Stein obtained a randomized contraction algorithm that finds a minimum $k$-cut in $O(n^{(2-o(1))k})$ time. It can also enumerate all such $k$-cuts in the same running time, establishing a corresponding extremal bound of $O(n^{(2-o(1))k})$. Since then, the algorithmic side of the minimum $k$-cut problem has seen much progress, leading to a deterministic algorithm based on a tree packing result of Thorup, which enumerates all minimum $k$-cuts in the same asymptotic running time, and gives an alternate proof of the $O(n^{(2-o(1))k})$ bound. However, beating the Karger--Stein bound, even for computing a single minimum $k$-cut, has remained out of reach. In this paper, we give an algorithm to enumerate all minimum $k$-cuts in $O(n^{(1.981+o(1))k})$ time, breaking the algorithmic and extremal barriers for enumerating minimum $k$-cuts. To obtain our result, we combine ideas from both the Karger--Stein and Thorup results, and draw a novel connection between minimum $k$-cut and extremal set theory. In particular, we give and use tighter bounds on the size of set systems with bounded dual VC-dimension, which may be of independent interest.

In the Dominating Set problem the input is a graph G and an integer k, the task is to determine whether there exists a vertex set S of size at most k so that every vertex not in S has at least one neighbor in S. We consider the parameterized complexity of the Dominating Set problem, parameterized by the solution size k, and the weak closure of the input graph G. Weak closure of graphs was recently introduced by Fox et al. [SIAM J. Comp. 2020 ] and captures sparseness and triadic closure properties found in real world graphs. A graph G is weakly c-closed if for every induced subgraph G' of G, there exists a vertex v ∈ V(G') such that every vertex u in V(G') which is non-adjacent to v has less than c common neighbors with v. The weak closure of G is the smallest integer γ such that G is weakly γ-closed. We give an algorithm for Dominating Set with running time k^O(γ² k³) n^O(1), resolving an open problem of Koana et al. [ISAAC 2020]. One of the ingredients of our algorithm is a proof that the VC-dimension of (the set system defined by the closed neighborhoods of the vertices of) a weakly γ-closed graph is upper bounded by 6γ. This result may find further applications in the study of weakly closed graphs.

We consider a multidimensional space partitioning problem, which we call Anonymity-Preserving Partition. Given a set P of n points in ℝ^d and a collection H of m axis-parallel hyperplanes, the hyperplanes of H partition the space into an arrangement A(H) of rectangular cells. Given an integer parameter t > 0, we call a cell C in this arrangement deficient if 0 < |C ∩ P| < t; that is, the cell contains at least one but fewer than t data points of P. Our problem is to remove the minimum number of hyperplanes from H so that there are no deficient cells. We show that the problem is NP-complete for all dimensions d ≥ 2. We present a polynomial-time d-approximation algorithm, for any fixed d, and we also show that the problem can be solved exactly in time (2d-0.924)^k m^O(1) + O(n), where k is the solution size. The one-dimensional case of the problem, where all hyperplanes are parallel, can be solved optimally in polynomial time, but we show that a related Interval Anonymity problem is NP-complete even in one dimension.

In the Min k-cut problem, input is an edge weighted graph G and an integer k, and the task is to partition the vertex set into k non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When k is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta et al. [SODA 2018] initiated the study of FPT-approximation for the Min k-Cut problem and gave an 1.9997-approximation algorithm running in time 2O(k6)nO(1). Later, the same set of authors [FOCS 2018] designed an ( 1+ε)-approximation algorithm that runs in time (k/ε)O(k)nk+O(1), and a 1.81-approximation algorithm running in time 2O(k2)nO(1). More, recently, Kawarabayashi and Lin [SODA 2020] gave a (5/3+ε)-approximation for Min k-Cut running in time 2O(k2logk)nO(1). In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the exponent). In particular, for every , the algorithm obtains a ( 1+ε)-approximate solution in time (k/ε)O(k)nO(1). The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time sO(k)nO(1)on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The latter two are of independent interest.