2024 [ nach oben ]

"Horev, Yinon"; "Shay, Shiraz"; "Cohen, Sarel"; "Friedrich, Tobias"; "Issac, Davis"; "Kamma, Lior"; "Niklanovits, Aikaterini"; "Simonov, Kirill" A Contraction Tree SAT Encoding for Computing Twin-Width 2024
[ Abstract ] [ BibTeX ] [ Download ]
 
Twin-width is a structural width parameter and matrix invariant introduced by Bonnet et al. [FOCS 2020], that has been gaining attention due to its various fields of applications. In this paper, inspired by the SAT approach of Schidler and Szeider [ALENEX 2022], we provide a new SAT encoding for computing twin-width. The encoding aims to encode the contraction sequence as a binary tree. The asymptotic size of the formula under our encoding is smaller than in the state-of-the-art relative encoding of Schidler and Szeider. We also conduct an experimental study, comparing the performance of the new encoding and the relative encoding.
@inproceedings{horev2024contraction, abstract = {Twin-width is a structural width parameter and matrix invariant introduced by Bonnet et al. [FOCS 2020], that has been gaining attention due to its various fields of applications. In this paper, inspired by the SAT approach of Schidler and Szeider [ALENEX 2022], we provide a new SAT encoding for computing twin-width. The encoding aims to encode the contraction sequence as a binary tree. The asymptotic size of the formula under our encoding is smaller than in the state-of-the-art relative encoding of Schidler and Szeider. We also conduct an experimental study, comparing the performance of the new encoding and the relative encoding.}, author = {"Horev, Yinon" and "Shay, Shiraz" and "Cohen, Sarel" and "Friedrich, Tobias" and "Issac, Davis" and "Kamma, Lior" and "Niklanovits, Aikaterini" and "Simonov, Kirill"}, keywords = {aikaterininiklanovits davisissac kirillsimonov liorkamma pakdd sarelcohen shirazshay tobiasfriedrich year2024 yinonhorev}, title = {A Contraction Tree SAT Encoding for Computing Twin-Width}, year = 2024 }

Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill Tree Containment Above Minimum Degree is FPTSymposium on Discrete Algorithms (SODA) 2024: 366–376
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Abstract According to the classic Chvatal's Lemma from 1977, a graph of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvatal's Lemma: For any \(n\)-vertex graph G, integer \(k\), and a tree \(T\) on at most \(\delta(G)+k\) vertices, deciding whether \(G\) contains a subgraph isomorphic to \(T\), can be done in time \(f(k) · n^\mathcal{O(1)}\) for some function \(f\) of \(k\) only. The proof of our main result is based on an interplay between extremal graph theory and parameterized algorithms. The full version of the paper can be accessed at https://arxiv.org/abs/2310.09678.
@inproceedings{fomin2024containment, abstract = {Abstract According to the classic Chvatal's Lemma from 1977, a graph of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvatal's Lemma: For any \(n\)-vertex graph G, integer \(k\), and a tree \(T\) on at most \(\delta(G)+k\) vertices, deciding whether \(G\) contains a subgraph isomorphic to \(T\), can be done in time \(f(k) · n^{\mathcal{O}(1)}\) for some function \(f\) of \(k\) only. The proof of our main result is based on an interplay between extremal graph theory and parameterized algorithms. The full version of the paper can be accessed at https://arxiv.org/abs/2310.09678.}, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {kirillsimonov soda year2024}, pages = {366-376}, title = {Tree Containment Above Minimum Degree is FPT}, year = 2024 }

2023 [ nach oben ]

Blažej, Václav; Ganian, Robert; Knop, Dušan; Pokorný, Jan; Schierreich, Šimon; Simonov, Kirill The Parameterized Complexity of Network MicroaggregationConference on Artificial Intelligence (AAAI) 2023: 6262–6270
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameteri- zations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.
@inproceedings{blazej2023parameterized, abstract = {Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameteri- zations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.}, author = {Blažej, Václav and Ganian, Robert and Knop, Dušan and Pokorný, Jan and Schierreich, Šimon and Simonov, Kirill}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {sys:relevantfor:ae aaai kirillsimonov year2023}, pages = {6262–6270}, title = {The Parameterized Complexity of Network Microaggregation}, year = 2023 }

Brand, Cornelius; Ganian, Robert; Simonov, Kirill A Parameterized Theory of PAC LearningConference on Artificial Intelligence (AAAI) 2023: 6834–6841
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexity. But while the nascent theory of parameterized complexity has allowed us to push beyond the P-NP “dichotomy” in classical computational complexity and identify the exact boundaries of tractability for numerous problems, there is no analogue in the domain of sample complexity that could push beyond efficient PAC learnability. As our core contribution, we fill this gap by developing a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity. Within the theory, we identify not one but two notions of fixed-parameter learnability that both form distinct counterparts to the class FPT—the core concept at the center of the parameterized complexity paradigm—and develop the machinery required to exclude fixed-parameter learnability. We then showcase the applications of this theory to identify refined boundaries of tractability for CNF and DNF learning as well as for a range of learning problems on graphs.
@inproceedings{brand2023parameterized, abstract = {Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexity. But while the nascent theory of parameterized complexity has allowed us to push beyond the P-NP “dichotomy” in classical computational complexity and identify the exact boundaries of tractability for numerous problems, there is no analogue in the domain of sample complexity that could push beyond efficient PAC learnability. As our core contribution, we fill this gap by developing a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity. Within the theory, we identify not one but two notions of fixed-parameter learnability that both form distinct counterparts to the class FPT—the core concept at the center of the parameterized complexity paradigm—and develop the machinery required to exclude fixed-parameter learnability. We then showcase the applications of this theory to identify refined boundaries of tractability for CNF and DNF learning as well as for a range of learning problems on graphs.}, author = {Brand, Cornelius and Ganian, Robert and Simonov, Kirill}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {sys:relevantfor:ae aaai kirillsimonov year2023}, pages = {6834–6841}, title = {A Parameterized Theory of PAC Learning}, year = 2023 }

Jansen, Bart M. P.; Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, Kirill Upward and Orthogonal Planarity are W[1]-Hard Parameterized by TreewidthGraph Drawing (GD) 2023: 203–217
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known \(n^{\mathcal{O(tw)}\)-time algorithms cannot be improved to run in time \(n^{o(tw)}\) unless ETH fails.
@inproceedings{DBLP:conf/gd/JansenKKLMS23, abstract = {Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard parameterized by treewidth, which answers open problems posed in two earlier papers. The key step in our proof is an analysis of the All-or-Nothing Flow problem, a generalization of which was used as an intermediate step in the NP-completeness proof for both planarity testing problems. We prove that the flow problem is W[1]-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known \(n^{\mathcal{O}(tw)}\)-time algorithms cannot be improved to run in time \(n^{o(tw)}\) unless ETH fails.}, author = {Jansen, Bart M. P. and Khazaliya, Liana and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio and Simonov, Kirill}, booktitle = {Graph Drawing (GD)}, keywords = {gd kirillsimonov year2023}, pages = {203–217}, title = {Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth}, year = 2023 }

Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill Approximating Long Cycle Above Dirac’s GuaranteeInternational Colloquium on Automata, Languages and Programming (ICALP) 2023: 60:1–60:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit “natural” guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m/2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n/2 + k for some \(k \geq 1\) and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree \(\delta(G) \leq n/2\), the length of a longest cycle L is at least \(2\delta(G)\). Thus the “essential” part in finding the longest cycle is in approximating the “offset” \(k = L − 2\delta(G)\). The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length \(2\delta(G) + \Omega(f(k))\).
@inproceedings{fomin2023approximating, abstract = {Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit “natural” guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m/2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n/2 + k for some \(k \geq 1\) and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree \(\delta(G) \leq n/2\), the length of a longest cycle L is at least \(2\delta(G)\). Thus the “essential” part in finding the longest cycle is in approximating the “offset” \(k = L − 2\delta(G)\). The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length \(2\delta(G) + \Omega(f(k))\).}, author = {Fomin, Fedor and Golovach, Petr and Sagunov, Danil and Simonov, Kirill}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sys:relevantfor:ae icalp kirillsimonov year2023}, pages = {60:1–60:18}, title = {Approximating Long Cycle Above Dirac’s Guarantee}, year = 2023 }

Ganian, Robert; Khazaliya, Liana; Simonov, Kirill Consistency Checking Problems: A Gateway to Parameterized Sample ComplexityInternational Symposium on Parameterized and Exact Computation (IPEC) 2023: 18:1–18:17
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Recently, Brand, Ganian and Simonov introduced a parameterized refinement of the classical PAC-learning sample complexity framework. A crucial outcome of their investigation is that for a very wide range of learning problems, there is a direct and provable correspondence between fixed-parameter PAC-learnability (in the sample complexity setting) and the fixed-parameter tractability of a corresponding “consistency checking” search problem (in the setting of computational complexity). The latter can be seen as generalizations of classical search problems where instead of receiving a single instance, one receives multiple yes- and no-examples and is tasked with finding a solution which is consistent with the provided examples. Apart from a few initial results, consistency checking problems are almost entirely unexplored from a parameterized complexity perspective. In this article, we provide an overview of these problems and their connection to parameterized sample complexity, with the primary aim of facilitating further research in this direction. Afterwards, we establish the fixed-parameter (in)-tractability for some of the arguably most natural consistency checking problems on graphs, and show that their complexity-theoretic behavior is surprisingly very different from that of classical decision problems. Our new results cover consistency checking variants of problems as diverse as (k-)Path, Matching, 2-Coloring, Independent Set and Dominating Set, among others.
@inproceedings{DBLP:conf/iwpec/GanianKS23, abstract = {Recently, Brand, Ganian and Simonov introduced a parameterized refinement of the classical PAC-learning sample complexity framework. A crucial outcome of their investigation is that for a very wide range of learning problems, there is a direct and provable correspondence between fixed-parameter PAC-learnability (in the sample complexity setting) and the fixed-parameter tractability of a corresponding “consistency checking” search problem (in the setting of computational complexity). The latter can be seen as generalizations of classical search problems where instead of receiving a single instance, one receives multiple yes- and no-examples and is tasked with finding a solution which is consistent with the provided examples. Apart from a few initial results, consistency checking problems are almost entirely unexplored from a parameterized complexity perspective. In this article, we provide an overview of these problems and their connection to parameterized sample complexity, with the primary aim of facilitating further research in this direction. Afterwards, we establish the fixed-parameter (in)-tractability for some of the arguably most natural consistency checking problems on graphs, and show that their complexity-theoretic behavior is surprisingly very different from that of classical decision problems. Our new results cover consistency checking variants of problems as diverse as (k-)Path, Matching, 2-Coloring, Independent Set and Dominating Set, among others.}, author = {Ganian, Robert and Khazaliya, Liana and Simonov, Kirill}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, keywords = {ipec kirillsimonov year2023}, pages = {18:1–18:17}, title = {Consistency Checking Problems: A Gateway to Parameterized Sample Complexity}, volume = 285, year = 2023 }

Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, Kirill The st-Planar Edge Completion Problem Is Fixed-Parameter TractableInternational Symposium Algorithms and Computation (ISAAC) 2023: 46:1–46:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The problem of deciding whether a biconnected planar digraph \(G = (V, E)\) can be augmented to become an st-planar graph by adding a set of oriented edges \(E′ \subseteq V \times V\) is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set \(E′\).
@inproceedings{DBLP:conf/isaac/KhazaliyaKLMS23, abstract = {The problem of deciding whether a biconnected planar digraph \(G = (V, E)\) can be augmented to become an st-planar graph by adding a set of oriented edges \(E′ \subseteq V \times V\) is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set \(E′\).}, author = {Khazaliya, Liana and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio and Simonov, Kirill}, booktitle = {International Symposium Algorithms and Computation (ISAAC)}, keywords = {isaac kirillsimonov year2023}, pages = {46:1–46:13}, title = {The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable}, year = 2023 }

Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Tuukka; Simonov, Kirill; Stamoulis Giannοs Fixed-Parameter Tractability of Maximum Colored Path and BeyondSymposium on Discrete Algorithms (SODA) 2023
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \($n$\)-vertex undirected graph, vertices \($s$\) and \($t$\), and an integer \($k$\), finds an \($(s,t)$\)-path containing at least \($k$\) different colors in time \($2^k n^\mathcal{O(1)}$\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman~[SODA~2012] on finding a path through \($k$\) specified vertices. It also implies the first \($2^k n^\mathcal{O(1)}$\) time algorithm for finding an \($(s,t)$\)-path of length at least \($k$\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \($n$\)-vertex undirected graph \($G$\), a matroid \($M$\) whose elements correspond to the vertices of \($G$\) and which is represented over a finite field of order \($q$\), a positive integer weight function on the vertices of \($G$\), two sets of vertices \($S,T subseteq V(G)$\), and integers \($p,k,w$\), and the task is to find \($p$\) vertex-disjoint paths from \($S$\) to \($T$\) so that the union of the vertices of these paths contains an independent set of \($M$\) of cardinality \($k$\) and weight \($w$\), while minimizing the sum of the lengths of the paths. We give a \($2^p+\mathcal{O(k^2 log (q+k)) n^\mathcal{O w$\) time randomized algorithm for this problem.
@inproceedings{fomin2023fixedparameter, abstract = {We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored $n$-vertex undirected graph, vertices $s$ and $t$, and an integer $k$, finds an $(s,t)$-path containing at least $k$ different colors in time $2^k n^{\mathcal{O}(1)}$. This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through $k$ specified vertices. It also implies the first $2^k n^{\mathcal{O}(1)}$ time algorithm for finding an $(s,t)$-path of length at least $k$. Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an $n$-vertex undirected graph $G$, a matroid $M$ whose elements correspond to the vertices of $G$ and which is represented over a finite field of order $q$, a positive integer weight function on the vertices of $G$, two sets of vertices $S,T \subseteq V(G)$, and integers $p,k,w$, and the task is to find $p$ vertex-disjoint paths from $S$ to $T$ so that the union of the vertices of these paths contains an independent set of $M$ of cardinality $k$ and weight $w$, while minimizing the sum of the lengths of the paths. We give a $2^{p+\mathcal{O}(k^2 \log (q+k))} n^{\mathcal{O}} w$ time randomized algorithm for this problem.}, author = {Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Simonov, Kirill and Stamoulis, Giannοs}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sys:relevantfor:ae kirillsimonov soda year2023}, title = {Fixed-Parameter Tractability of Maximum Colored Path and Beyond}, year = 2023 }

Bandyapadhyay, Sayan; Fomin, Fedor V.; Inamdar, Tanmay; Panolan, Fahad; Simonov, Kirill Socially Fair Matching: Exact and Approximation AlgorithmsWorkshop on Algorithms and Data Structures (WADS) 2023: 79–92
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Matching problems are some of the most well-studied problems in graph theory and combinatorial optimization, with a variety of theoretical as well as practical motivations. However, in many applications of optimization problems, a ``solution'' corresponds to real-life decisions that have major impact on humans belonging to diverse groups defined by attributes such as gender, race, or ethnicity. Due to this motivation, the notion of \emph{algorithmic fairness has recently emerged to prominence. Depending on specific application, researchers have introduced several notions of fairness. In this paper, we study a problem called ``Socially Fair Matching'', which combines the traditional Minimum Weight Perfect Matching problem with the notion of social fairness that has been studied in clustering literature [Abbasi et al., and Ghadiri et al., FAccT, 2021]. In our problem, the input is an edge-weighted complete bipartite graph, where the bipartition represent two groups of entities. The goal is to find a perfect matching as well as an assignment that assigns the cost of each matched edge to one of its endpoints, such that the maximum of the total cost assigned to either of the two groups is minimized. Unlike Minimum Weight Perfect Matching, we show that Socially Fair Matching is weakly NP-hard. On the positive side, we design a deterministic PTAS for the problem when the edge weights are arbitrary. Furthermore, if the weights are integers and polynomial in the number of vertices, then we give a randomized polynomial-time algorithm that solves the problem exactly. Next, we show that this algorithm can be used to obtain a randomized FPTAS when the weights are arbitrary.
@inproceedings{bandyapadhyay2023socially, abstract = {Matching problems are some of the most well-studied problems in graph theory and combinatorial optimization, with a variety of theoretical as well as practical motivations. However, in many applications of optimization problems, a ``solution'' corresponds to real-life decisions that have major impact on humans belonging to diverse groups defined by attributes such as gender, race, or ethnicity. Due to this motivation, the notion of \emph{algorithmic fairness} has recently emerged to prominence. Depending on specific application, researchers have introduced several notions of fairness. In this paper, we study a problem called ``Socially Fair Matching'', which combines the traditional Minimum Weight Perfect Matching problem with the notion of social fairness that has been studied in clustering literature [Abbasi et al., and Ghadiri et al., FAccT, 2021]. In our problem, the input is an edge-weighted complete bipartite graph, where the bipartition represent two groups of entities. The goal is to find a perfect matching as well as an assignment that assigns the cost of each matched edge to one of its endpoints, such that the maximum of the total cost assigned to either of the two groups is minimized. Unlike Minimum Weight Perfect Matching, we show that Socially Fair Matching is weakly NP-hard. On the positive side, we design a deterministic PTAS for the problem when the edge weights are arbitrary. Furthermore, if the weights are integers and polynomial in the number of vertices, then we give a randomized polynomial-time algorithm that solves the problem exactly. Next, we show that this algorithm can be used to obtain a randomized FPTAS when the weights are arbitrary.}, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Inamdar, Tanmay and Panolan, Fahad and Simonov, Kirill}, booktitle = {Workshop on Algorithms and Data Structures (WADS)}, keywords = {sys:relevantfor:ae kirillsimonov wads year2023}, pages = {79–92}, title = {Socially Fair Matching: Exact and Approximation Algorithms}, year = 2023 }

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
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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.
@inproceedings{bandyapadhyay2023proportionally, abstract = {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.}, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Inamdar, Tanmay and Simonov, Kirill}, booktitle = {Workshop on Graph-Theoretic Concepts in Computer Science (WG)}, keywords = {sys:relevantfor:ae kirillsimonov wg year2023}, pages = {1–15}, title = {Proportionally Fair Matching with Multiple Groups}, year = 2023 }

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
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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.
@inproceedings{fomin2023turns, abstract = {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.}, author = {Fomin, Fedor and Golovach, Petr and Sagunov, Danil and Simonov, Kirill}, booktitle = {Workshop on Graph-Theoretic Concepts in Computer Science (WG)}, keywords = {sys:relevantfor:ae kirillsimonov wg year2023}, pages = {348–362}, title = {Turán’s Theorem Through Algorithmic Lens}, year = 2023 }

2022 [ nach oben ]

Bandyapadhyay, Sayan; Fomin, Fedor V.; Golovach, Petr A.; Lochet, William; Purohit, Nidhi; Simonov, Kirill How to Find a Good Explanation for Clustering?Conference on Artificial Intelligence (AAAI) 2022: 3904–3912
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
\(k\)-means and \(k\)-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable \(k\)-means and \(k\)-median clustering in ICML 2020. In this model, a decision tree with \(k\) leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with \(k\) leaves? (2) For a given set of points, how to find a decision tree with \(k\) leaves minimizing the \(k\)-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.
@inproceedings{bandyapadhyay2022explanation, abstract = {\(k\)-means and \(k\)-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable \(k\)-means and \(k\)-median clustering in ICML 2020. In this model, a decision tree with \(k\) leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with \(k\) leaves? (2) For a given set of points, how to find a decision tree with \(k\) leaves minimizing the \(k\)-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.}, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Purohit, Nidhi and Simonov, Kirill}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {sys:relevantfor:ae aaai kirillsimonov year2022}, pages = {3904-3912}, title = {How to Find a Good Explanation for Clustering?}, year = 2022 }

Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill Algorithmic Extensions of Dirac’s TheoremSymposium on Discrete Algorithms (SODA) 2022: 406–416
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \(n\)-vertex undirected graph, vertices \(s\) and \(t\), and an integer \(k\), finds an \((s,t)\)-path containing at least \(k\) different colors in time \(2^k n^\mathcal{O(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through \(k\) specified vertices. It also implies the first \(2^k n^\mathcal{O(1)}\) time algorithm for finding an \(s,t)\)-path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\)-vertex undirected graph \(G\), a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\), a positive integer weight function on the vertices of \(G\), two sets of vertices \(S,T subseteq V(G)\), and integers \(p,k,w\), and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\), while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O(k^2 log (q+k)) n^\mathcal{O(1) w\) time randomized algorithm for this problem.
@inproceedings{fomin2022algorithmic, abstract = {We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \(n\)-vertex undirected graph, vertices \(s\) and \(t\), and an integer \(k\), finds an \((s,t)\)-path containing at least \(k\) different colors in time \(2^k n^{\mathcal{O}(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Bj{ö}rklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through \(k\) specified vertices. It also implies the first \(2^k n^{\mathcal{O}(1)}\) time algorithm for finding an \(s,t)\)-path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\)-vertex undirected graph \(G\), a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\), a positive integer weight function on the vertices of \(G\), two sets of vertices \(S,T \subseteq V(G)\), and integers \(p,k,w\), and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\), while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^2 \log (q+k))} n^{\mathcal{O}(1)} w\) time randomized algorithm for this problem.}, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sys:relevantfor:ae kirillsimonov soda year2022}, pages = {406-416}, title = {Algorithmic Extensions of Dirac's Theorem}, year = 2022 }