Abstract In the general AntiFactor problem, a graph G and, for every vertex v of G, a set $$X_v\subseteq {\mathbb {N}}$$ X v ⊆ N of forbidden degrees is given. The task is to find a set S of edges such that the degree of v in S is not in the set $$X_v$$ X v . Standard techniques (dynamic programming plus fast convolution) can be used to show that if M is the largest forbidden degree, then the problem can be solved in time $$(M+2)^{{\operatorname {tw}}}\cdot n^{{\mathcal {O}}(1)}$$ ( M + 2 ) tw · n O ( 1 ) if a tree decomposition of width $${\operatorname {tw}}$$ tw is given. However, significantly faster algorithms are possible if the sets $$X_v$$ X v are sparse: our main algorithmic result shows that if every vertex has at most $$x$$ x forbidden degrees (we call this special case AntiFactor x), then the problem can be solved in time $$(x+1)^{{\mathcal {O}}({\operatorname {tw}})}\cdot n^{{\mathcal {O}}(1)}$$ ( x + 1 ) O ( tw ) · n O ( 1 ) . That is, AntiFactor x is fixed-parameter tractable parameterized by treewidth $${\operatorname {tw}}$$ tw and the maximum number $$x$$ x of excluded degrees. Our algorithm uses the technique of representative sets, which can be generalized to the optimization version, but (as expected) not to the counting version of the problem. In fact, we show that #AntiFactor 1 is already # $$[1]$$ [ 1 ] -hard parameterized by the width of the given decomposition. Moreover, we show that, unlike for the decision version, the standard dynamic programming algorithm is essentially optimal for the counting version. Formally, for a fixed nonempty set $$X$$ X , we denote by $$X$$ X -AntiFactor the special case where every vertex v has the same set $$X_v=X$$ X v = X of forbidden degrees. We show the following lower bound for every fixed set $$X$$ X : if there is an $$\epsilon >0$$ ϵ > 0 such that # $$X$$ X -AntiFactor can be

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\) -set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\) , and \(|N(\!\textit{v})\cap S|\in\rho\) for every \(\textit{v}\not\in S\) . The problem of finding a \((\sigma,\rho)\) -set (of a certain size) unifies standard problems, such as Independent Set , Dominating Set , Independent Dominating Set , and many others. For all pairs of finite or cofinite sets \((\sigma,\rho)\) , we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) (if a tree decomposition of width \(\textsf{tw}\) is given in the input). Let \(s_{{\rm top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{{\rm top}}\) is defined analogously for \(\rho\) . Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{{\rm top}}+r_{{\rm top}}+2\) achieved by existing algorithms. Toward defining \(c_{\sigma,\rho}\) , we say that \((\sigma,\rho)\) is \({\mathrm{m}}\) -structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod \({\mathrm{m}}\) , and every integer in \(\rho\) equals \(\beta\) mod \({\mathrm{m}}\) . Then, setting — \(c_{\sigma,\rho}=s_{{\rm top}}+r_{{\rm top}}+2\) if \((\sigma,\rho)\) is not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 2\) , — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 3\) , and

In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters that are cohesive in that close by pairs of nodes are assigned to the same cluster with high probability. We consider the additional aspect of individual fairness – pairs of nodes at comparable distances should be separated with comparable probability. We show that classic decomposition procedures do not satisfy this property. We present novel algorithms that achieve various trade-offs between this property and additional desiderata of connectivity of the clusters and optimality in number of clusters. We show that our individual fairness bounds may be difficult to improve by tying the improvement to resolving a major open question in metric embeddings. We finally show the efficacy of our algorithms on real planar networks modeling Congressional redistricting.

This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from other agents. The goal of the marketplace is to encourage participation for data sharing in the presence of such heterogeneity. Our market design approach for data sharing focuses on interim utility balance, where participants contribute and receive equitable utility from refinement of their models. We present such a market model for which we study computational complexity, solution existence, and approximation algorithms for welfare maximization and core stability. We finally support our theoretical insights with simulations on a mean estimation task inspired by road traffic delay estimation.

Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. Moreover, online matching problems have lots of applications in ad allocations and other e-commerce problems like product recommendation in digital marketing. We study two problems involving assigning items to platforms, where items belong to various groups depending on their attributes; the set of items are available offline and the platforms arrive online. In the first problem, we study online matchings with proportional fairness constraints. Here, each platform on arrival should either be assigned a set of items in which the fraction of items from each group is within specified bounds or be assigned no items; the goal is to assign items to platforms in order to maximize the number of items assigned to platforms. In the second problem, we study online matchings with diversity constraints, i.e. for each platform, absolute lower bounds are specified for each group. Each platform on arrival should either be assigned a set of items that satisfy these bounds or be assigned no items; the goal is to maximize the set of platforms that get matched. We study approximation algorithms and hardness results for these problems. The technical core of our proofs is a new connection between these problems and the problem of matchings in hypergraphs. Our experimental evaluation shows the performance of our algorithms on real-world and synthetic datasets exceeds our theoretical guarantees.

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that | N (u) ∩ S| ∈ σ for every u ∈ S, and | N (v) ∩ S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as INDEPENDENT SET, DOMINATING SET, INDEPENDENT DOMINATING SET, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value cσ,ρ such that there is an algorithm that counts (σ, ρ)-sets in time ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite; rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining cσ,ρ, we say that (σ,ρ) is m-structured if there is a pair (α,β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • cσ,ρ = stop + rtop +2 if (σ, ρ) is not m-structured for any m ≥ 2 • cσ,ρ = max{stop,rtop} + 2 if (σ,ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the EXACT INDEPENDENT DOMINATING SET problem (also known as PERFECT CODE) corresponding to σ = {0} and ρ = {1}, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw· nO(1). Despite the unusually delicate definition of cσ,ρ, we show that our algorithms are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a (cσ,ρ — ε)tw · nO(1)- algorithm counting the number of (σ, ρ)-sets would violate the COUNTING STRONG EXPONENTIAL-TIME HYPOTHESIS (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets. * The full version of this work can be accessed at https://arxiv.org/abs/2211.04278. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

In the general AntiFactor problem, a graph G and, for every vertex v of G, a set X_v ⊆ ℕ of forbidden degrees is given. The task is to find a set S of edges such that the degree of v in S is not in the set X_v. Standard techniques (dynamic programming plus fast convolution) can be used to show that if M is the largest forbidden degree, then the problem can be solved in time (M+2)^{tw}⋅n^{O(1)} if a tree decomposition of width tw is given. However, significantly faster algorithms are possible if the sets X_v are sparse: our main algorithmic result shows that if every vertex has at most x forbidden degrees (we call this special case AntiFactor_x), then the problem can be solved in time (x+1)^{O(tw)}⋅n^{O(1)}. That is, AntiFactor_x is fixed-parameter tractable parameterized by treewidth tw and the maximum number x of excluded degrees. Our algorithm uses the technique of representative sets, which can be generalized to the optimization version, but (as expected) not to the counting version of the problem. In fact, we show that #AntiFactor₁ is already #W[1]-hard parameterized by the width of the given decomposition. Moreover, we show that, unlike for the decision version, the standard dynamic programming algorithm is essentially optimal for the counting version. Formally, for a fixed nonempty set X, we denote by X-AntiFactor the special case where every vertex v has the same set X_v = X of forbidden degrees. We show the following lower bound for every fixed set X: if there is an ε > 0 such that #X-AntiFactor can be solved in time (max X+2-ε)^{tw}⋅n^{O(1)} given a tree decomposition of width tw, then the Counting Strong Exponential-Time Hypothesis (#SETH) fails.

For the General Factor problem we are given an undirected graph $G$ and for each vertex $v\in V(G)$ a finite set $B_v$ of non-negative integers. The task is to decide if there is a subset $S\subseteq E(G)$ such that $deg_S(v)\in B_v$ for all vertices $v$ of $G$. The maxgap of a finite integer set $B$ is the largest $d\ge 0$ such that there is an $a\ge 0$ with $[a,a+d+1]\cap B=\{a,a+d+1\}$. Cornuéjols (1988) showed that if the maxgap of all sets $B_v$ is at most 1, then the decision version of General Factor is poly-time solvable. Dudycz and Paluch (2018) extended this result for the minimization and maximization versions. Using convolution techniques from van Rooij (2020), we improve upon the previous algorithm by Arulselvan et al. (2018) and present an algorithm counting the number of solutions of a certain size in time $O^*((M+1)^k)$, given a tree decomposition of width $k$, where $M=\max_v \max B_v$. We prove that this algorithm is essentially optimal for all cases that are not polynomial time solvable for the decision, minimization or maximization versions. We prove that such improvements are not possible even for $B$-Factor, which is General Factor on graphs where all sets $B_v$ agree with the fixed set $B$. We show that for every fixed $B$ where the problem is NP-hard, our new algorithm cannot be significantly improved: assuming the Strong Exponential Time Hypothesis (SETH), no algorithm can solve $B$-Factor in time $O^*((\max B+1-ε)^k)$ for any $ε>0$. We extend this bound to the counting version of $B$-Factor for arbitrary, non-trivial sets $B$, assuming #SETH. We also investigate the parameterization of the problem by cutwidth. Unlike for treewidth, a larger set $B$ does not make the problem harder: Given a linear layout of width $k$ we give a $O^*(2^k)$ algorithm for any $B$ and provide a matching lower bound that this is optimal for the NP-hard cases.

We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this paper. Each platform specifies the group fairness constraints through an upper bound on the number of items it can serve from each class. Additionally, each platform also has an upper bound on the total number of items it can serve. The goal is to assign items to platforms so as to maximize the number of items assigned while satisfying the upper bounds of each class. This problem models several important real-world problems like ad-auctions, scheduling, resource allocations, school choice etc. We show that if the classes are arbitrary, then the problem is NP-hard and has a strong inapproximability. We consider the problem in both online and offline settings under natural restrictions on the classes. Under these restrictions, the problem continues to remain NP-hard but admits approximation algorithms with small approximation factors. We also implement some of the algorithms. Our experiments show that the algorithms work well in practice both in terms of efficiency and the number of items that get assigned to some platform.