Abstract In the Token Sliding problem we are given a graph G and two independent sets $$I_s$$ I s and $$I_t$$ I t in G of size $$k \ge 1$$ k ≥ 1 . The goal is to decide whether there exists a sequence $$\langle I_1, I_2, \ldots , I_\ell \rangle $$ ⟨ I 1 , I 2 , … , I ℓ ⟩ of independent sets such that for all $$j \in \{1,\ldots , \ell - 1\}$$ j ∈ { 1 , … , ℓ - 1 } the set $$I_j$$ I j is an independent set of size k, $$I_1 = I_s$$ I 1 = I s , $$I_\ell = I_t$$ I ℓ = I t and $$I_j \triangle I_{j + 1} = \{u, v\} \in E(G)$$ I j ▵ I j + 1 = { u , v } ∈ E ( G ) . Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms $$I_s$$ I s into $$I_t$$ I t where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by k. As shown by Bartier et al. (Algorithmica 83(9):2914–2951, 2021. https://doi.org/10.1007/s00453-021-00848-1 ), the problem is -hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant $$p \ge 5$$ p ≥ 5 such that the problem becomes fixed-parameter tractable on graphs of girth at least p. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph.

Abstract As the number of online labor platforms and the diversity of jobs on these platforms increase, ensuring group fairness for workers needs to be the focus of job-matching services. Risk of discrimination against workers occurs in two different job-matching services: when someone is looking for a job (i.e., a job seeker) and when someone wants to deploy jobs (i.e., a job provider). To maximize their chances of getting hired, job seekers submit their profiles on different platforms. Similarly, job providers publish their job offers on multiple platforms with the goal of reaching a wide and diverse workforce. In this paper, we propose a theoretical framework to maximize group fairness for workers 1) when job seekers are looking for jobs on multiple platforms, and 2) when jobs are being deployed by job providers on multiple platforms. We formulate each goal as different optimization problems with different constraints, prove most of them are computationally hard to solve and propose various efficient algorithms to solve all of them in reasonable time. We then design a series of experiments that rely on synthetic and semi-synthetic data generated from a real-world online labor platform to evaluate our framework.