Abstract
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 AB ≤ 1 and the number k of edges between A and B is minimized. The problem is known to be NPhard, and assuming the Unique Games Conjecture even NPhard 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 reformulated 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 almostequal 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 underrepresented 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 FPTapproximation algorithms for problems of bounded treewidth or cliquewidth 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.
BibTeX  Entry
@InProceedings{inamdar_et_al:LIPIcs.ESA.2023.63,
author = {Inamdar, Tanmay and Lokshtanov, Daniel and Saurabh, Saket and Surianarayanan, Vaishali},
title = {{Parameterized Complexity of Fair Bisection: (FPTApproximation meets Unbreakability)}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {63:163:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18716},
URN = {urn:nbn:de:0030drops187167},
doi = {10.4230/LIPIcs.ESA.2023.63},
annote = {Keywords: FPT Approximation, Minimum Bisection, Unbreakable Tree Decomposition, Treewidth}
}
Keywords: 

FPT Approximation, Minimum Bisection, Unbreakable Tree Decomposition, Treewidth 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 