Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill Turán’s Theorem Through Algorithmic LensWorkshop on Graph-Theoretic Concepts in Computer Science (WG) 2023: 348–362
The fundamental theorem of Tur{á}n from Extremal Graph Theory determines the exact bound on the number of edges \($t_r(n)$\) in an \($n$\)-vertex graph that does not contain a clique of size \($r+1$\). We establish an interesting link between Extremal Graph Theory and Algorithms by providing a simple compression algorithm that in linear time reduces the problem of finding a clique of size \($\ell$\) in an \($n$\)-vertex graph \($G$\) with \($m ge t_r(n)-k$\) edges, where \($\ell\leq r+1$\), to the problem of finding a maximum clique in a graph on at most \($5k$\) vertices. This also gives us an algorithm deciding in time \($2.49^{k}\cdot(n + m)$\) whether \($G$\) has a clique of size \($\ell$\). As a byproduct of the new compression algorithm, we give an algorithm that in time \($2^{\mathcal{O}(td^2 )} \cdot n^2$\) decides whether a graph contains an independent set of size at least \($n/(d+1) +t$\). Here \($d$\) is the average vertex degree of the graph \($G$\). The multivariate complexity analysis based on ETH indicates that the asymptotical dependence on several parameters in the running times of our algorithms is tight.
Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal GraphsWorkshop Graph-Theoretic Concepts in Computer Science (WG) 2023: 143–156
In the 1970s, Gy\H{o}ri and Lov{á}sz showed that for a \(k\)-connected \(n\)-vertex graph, a given set of terminal vertices \(t_1, \dots, t_k\) and natural numbers \(n_1, \dots, n_k\) satisfying \(\sum_{i=1}^{k} n_i = n\), a connected vertex partition \(S_1, \dots, S_k\) satisfying \(t_i \in S_i\) and \(|S_i| = n_i\) exists. However, polynomial algorithms to actually compute such partitions are known so far only for \(k \leq 4\). This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of \(k\). More precisely, we consider \(k\)-connected chordal graphs and a broader class of graphs related to them. For the first class, we give an algorithm with \(\mathcal{O}(n^2)\) running time that solves the problem exactly, and for the second, an algorithm with \(\mathcal{O}(n^4)\) running time that deviates on at most one vertex from the required vertex partition sizes.
Bandyapadhyay, Sayan; Fomin, Fedor V.; Inamdar, Tanmay; Simonov, Kirill Proportionally Fair Matching with Multiple GroupsWorkshop on Graph-Theoretic Concepts in Computer Science (WG) 2023: 1–15
We study matching problems with the notion of proportional fairness. Proportional fairness is one of the most popular notions of group fairness where every group is represented up to an extent proportional to the final selection size. Matching with proportional fairness or more commonly, proportionally fair matching, was introduced in [Chierichetti et al., AISTATS, 2019]. In this problem, we are given a graph \($G$\) whose edges are colored with colors from a set \($C$\). The task is for given \($0\le \alpha \le \beta \le 1$\), to find a maximum \($(\alpha,\beta)$\)-balanced matching \($M$\) in \($G$\), that is a matching where for every color \($c\in C$\) the number of edges in \($M$\) of color \($c$\) is between \($\alpha|M|$\) and \($\beta |M|$\). Chierichetti et al. initiated the study of this problem with two colors and in the context of bipartite graphs only. However, in many practical applications, the number of colors---although often a small constant---is larger than two. In this work, we make the first step towards understanding the computational complexity of proportionally fair matching with more than two colors. We design exact and approximation algorithms achieving reasonable guarantees on the quality of the matching as well as on the time complexity, and our algorithms work in general graphs. Our algorithms are also supported by suitable hardness bounds.