Nadym Mallek

2026 [ nach oben ]

Mallek, Nadym; Simonov, Kirill Optimal Approximations for the Requirement Cut Problem on Sparse Graph ClassesInternational Conference on Current Trends in Theory and Practice of Computer Science 2026: 547–562
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the Requirement Cut problem, a generalization of numerous classical graph partitioning problems including Multicut, Multiway Cut, k-Cut, and Steiner Multicut among others. Given a graph with edge costs, terminal groups (S_1, ..., S_g) and integer requirements (r_1,... , r_g); the goal is to compute a minimum-cost edge cut that separates each group S_i into at least r_i connected components. Despite many efforts, the best known approximation for Requirement Cut yields a double-logarithmic O(\log(g).\log(n)) approximation ratio as it relies on embedding general graphs into trees and solving the tree instance. In this paper, we explore two largely unstudied structural parameters in order to obtain single-logarithmic approximation ratios: (1) the number of minimal Steiner trees in the instance, which in particular is upper-bounded by the number of spanning trees of the graphs multiplied by g, and (2) the depth of series-parallel graphs. Specifically, we show that if the number of minimal Steiner trees is polynomial in n, then a simple LP-rounding algorithm yields an O(\log n)-approximation, and if the graph is series-parallel with a constant depth then a refined analysis of a known probabilistic embedding yields a O(depth.\log(g))-approximation on series-parallel graphs of bounded depth. Both results extend the known class of graphs that have a single-logarithmic approximation ratio.
@inproceedings{ms-oaotrcposgc-2026, abstract = {We study the Requirement Cut problem, a generalization of numerous classical graph partitioning problems including Multicut, Multiway Cut, k-Cut, and Steiner Multicut among others. Given a graph with edge costs, terminal groups (S_1, ..., S_g) and integer requirements (r_1,... , r_g); the goal is to compute a minimum-cost edge cut that separates each group S_i into at least r_i connected components. Despite many efforts, the best known approximation for Requirement Cut yields a double-logarithmic O(\log(g).\log(n)) approximation ratio as it relies on embedding general graphs into trees and solving the tree instance. In this paper, we explore two largely unstudied structural parameters in order to obtain single-logarithmic approximation ratios: (1) the number of minimal Steiner trees in the instance, which in particular is upper-bounded by the number of spanning trees of the graphs multiplied by g, and (2) the depth of series-parallel graphs. Specifically, we show that if the number of minimal Steiner trees is polynomial in n, then a simple LP-rounding algorithm yields an O(\log n)-approximation, and if the graph is series-parallel with a constant depth then a refined analysis of a known probabilistic embedding yields a O(depth.\log(g))-approximation on series-parallel graphs of bounded depth. Both results extend the known class of graphs that have a single-logarithmic approximation ratio.}, author = {Mallek, Nadym and Simonov, Kirill}, booktitle = {International Conference on Current Trends in Theory and Practice of Computer Science}, editor = {Kozik, Jakub and Wolff, Alexander}, keywords = {sys:relevantfor:ae kirillsimonov nadymmallek sofsem year2026}, pages = {547–562}, title = {Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes}, year = 2026 }

2025 [ nach oben ]

Filtser, Arnold; Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Le, Hung; Mallek, Nadym; Zeif, Ziena Optimal Padded Decomposition For Bounded Treewidth GraphsTheoretiCS 2025
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A \((\beta,\delta,\Delta)\)-padded decomposition of an edge-weighted graph \(G = (V,E,w)\) is a stochastic decomposition into clusters of diameter at most \(\Delta\) such that for every vertex \(v\in V\), the probability that \(\ball_G(v,\gamma\Delta)\) is entirely contained in the cluster containing \(v\) is at least \(e^{-\beta\gamma}\) for every \(\gamma \in [0,\delta]\). Padded decompositions have been studied for decades and have found numerous applications, including metric embedding, multicommodity flow-cut gap, multicut, and zero extension problems, to name a few. In these applications, parameter \(\beta\), called the \emph{padding parameter, is the most important parameter since it decides either the distortion or the approximation ratios. For general graphs with \(n\) vertices, the \emph{padding parameter \(\beta\) is known to be in \(\Theta(\log n)\). Klein, Plotkin, and Rao [KPR93] (KPR) showed that \(K_r\)-minor-free graphs have padding parameter \(beta = \mathcal{O(r^3)\), which is a significant improvement over general graphs when \(r\) is a constant. However, when \(r= \Omega(\log n)\), the padding parameter in KPR decomposition can be much worse than \(\log n\). A long-standing conjecture is that constructing a padded decomposition for \(K_r\)-minor-free graphs is possible with padding parameter \(beta = \mathcal{O(\log r)\). Despite decades of research, the best-known result is \(beta = \mathcal{O(r)\), even for graphs with treewidth at most \(r\). In this work, we make significant progress toward the aforementioned conjecture by showing that graphs with treewidth \(\tw\) admit a padded decomposition with padding parameter \(\mathcal{O(\log \tw)\), which is tight. Our padding parameter is strictly better than \(\mathcal{O(\log n)\) whenever \(tw = n^o(1)}\), and is never worse than what is known for general graphs. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: \(\mathcal{O(\sqrt{ log n cdot \log(\tw)})\) flow-cut gap, the maxflow-min multicut ratio of \(\mathcal{O(\log(\tw))\), an \(\mathcal{O(\log(\tw))\) approximation for the 0-extension problem, an \(\ell^{\mathcal{O(\log n)}_\infty\) embedding with distortion \(\mathcal{O(\log \tw)\), and an \(\mathcal{O(\log \tw)\) bound for integrality gap for the uniform sparsest cut.
@article{filtser2025optimal, abstract = {A \((\beta,\delta,\Delta)\)-padded decomposition of an edge-weighted graph \(G = (V,E,w)\) is a stochastic decomposition into clusters of diameter at most \(\Delta\) such that for every vertex \(v\in V\), the probability that \(\ball_G(v,\gamma\Delta)\) is entirely contained in the cluster containing \(v\) is at least \(e^{-\beta\gamma}\) for every \(\gamma \in [0,\delta]\). Padded decompositions have been studied for decades and have found numerous applications, including metric embedding, multicommodity flow-cut gap, multicut, and zero extension problems, to name a few. In these applications, parameter \(\beta\), called the \emph{padding parameter}, is the most important parameter since it decides either the distortion or the approximation ratios. For general graphs with \(n\) vertices, the \emph{padding parameter} \(\beta\) is known to be in \(\Theta(\log n)\). Klein, Plotkin, and Rao [KPR93] (KPR) showed that \(K_r\)-minor-free graphs have padding parameter \(\beta = \mathcal{O}(r^3)\), which is a significant improvement over general graphs when \(r\) is a constant. However, when \(r= \Omega(\log n)\), the padding parameter in KPR decomposition can be much worse than \(\log n\). A long-standing conjecture is that constructing a padded decomposition for \(K_r\)-minor-free graphs is possible with padding parameter \(\beta = \mathcal{O}(\log r)\). Despite decades of research, the best-known result is \(\beta = \mathcal{O}(r)\), even for graphs with treewidth at most \(r\). In this work, we make significant progress toward the aforementioned conjecture by showing that graphs with treewidth \(\tw\) admit a padded decomposition with padding parameter \(\mathcal{O}(\log \tw)\), which is tight. Our padding parameter is strictly better than \(\mathcal{O}(\log n)\) whenever \(\tw = n^{o(1)}\), and is never worse than what is known for general graphs. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: \(\mathcal{O}(\sqrt{ \log n \cdot \log(\tw)})\) flow-cut gap, the maxflow-min multicut ratio of \(\mathcal{O}(\log(\tw))\), an \(\mathcal{O}(\log(\tw))\) approximation for the 0-extension problem, an \(\ell^{\mathcal{O}(\log n)}_\infty\) embedding with distortion \(\mathcal{O}(\log \tw)\), and an \(\mathcal{O}(\log \tw)\) bound for integrality gap for the uniform sparsest cut.}, author = {Filtser, Arnold and Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Le, Hung and Mallek, Nadym and Zeif, Ziena}, journal = {TheoretiCS}, keywords = {sys:relevantfor:ae davisissac nadymmallek nikhilkumar theoretics tobiasfriedrich year2025 zienazeif}, title = {Optimal Padded Decomposition For Bounded Treewidth Graphs}, year = 2025 }

Schmidt, Jonas; Verma, Shaily; Mallek, Nadym A Parameterized Study of Secluded Structures in Directed Graphs 2025: 53:1–53:21
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given an undirected graph G and an integer k, the Secluded Pi-Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property Pi and has at most k neighbors in the rest of the graph. This problem has been extensively studied; however, there is no prior study of the problem in directed graphs. This question has been mentioned by Jansen et al. [ISAAC'23]. In this paper, we initiate the study of Secluded Subgraph problem in directed graphs by incorporating different notions of neighborhoods: in-neighborhood, out-neighborhood, and their union. Formally, we call these problems \\text{In}, \text{Out, \text{Total-Secluded Pi-Subgraph, where given a directed graph G and integers k, we want to find an induced subgraph satisfying Pi of maximum size that has at most k in/out/total-neighbors in the rest of the graph, respectively. We investigate the parameterized complexity of these problems for different properties Pi. In particular, we prove the following parameterized results: - We design an FPT algorithm for the Total-Secluded Strongly Connected Subgraph problem when parameterized by k. - We show that the In/Out-Secluded \mathcal{F-Free Subgraph problem with parameter k+w is W[1]-hard, where \mathcal{F is a family of directed graphs except any subgraph of a star graph whose edges are directed towards the center. This result also implies that In/Out-Secluded DAG is W[1]-hard, unlike the undirected variants of the two problems, which are FPT. - We design an FPT-algorithm for In/Out/Total-Secluded alpha-Bounded Subgraph when parameterized by k, where alpha-bounded graphs are a superclass of tournaments. - For undirected graphs, we improve the best-known FPT algorithm for Secluded Clique by providing a faster FPT algorithm that runs in time 1.6181^kn^\mathcal{O(1).
@inproceedings{svm-apsossidg-2025, abstract = {Given an undirected graph G and an integer k, the Secluded \Pi-Subgraph problem asks you to find a maximum size induced subgraph that satisfies a property \Pi and has at most k neighbors in the rest of the graph. This problem has been extensively studied; however, there is no prior study of the problem in directed graphs. This question has been mentioned by Jansen et al. [ISAAC'23]. In this paper, we initiate the study of Secluded Subgraph problem in directed graphs by incorporating different notions of neighborhoods: in-neighborhood, out-neighborhood, and their union. Formally, we call these problems \{\text{In}, \text{Out}, \text{Total}\}-Secluded \Pi-Subgraph, where given a directed graph G and integers k, we want to find an induced subgraph satisfying \Pi of maximum size that has at most k in/out/total-neighbors in the rest of the graph, respectively. We investigate the parameterized complexity of these problems for different properties \Pi. In particular, we prove the following parameterized results: - We design an FPT algorithm for the Total-Secluded Strongly Connected Subgraph problem when parameterized by k. - We show that the In/Out-Secluded \mathcal{F}-Free Subgraph problem with parameter k+w is W[1]-hard, where \mathcal{F} is a family of directed graphs except any subgraph of a star graph whose edges are directed towards the center. This result also implies that In/Out-Secluded DAG is W[1]-hard, unlike the undirected variants of the two problems, which are FPT. - We design an FPT-algorithm for In/Out/Total-Secluded \alpha-Bounded Subgraph when parameterized by k, where \alpha-bounded graphs are a superclass of tournaments. - For undirected graphs, we improve the best-known FPT algorithm for Secluded Clique by providing a faster FPT algorithm that runs in time 1.6181^kn^{\mathcal{O}(1)}.}, author = {Schmidt, Jonas and Verma, Shaily and Mallek, Nadym}, keywords = {sys:relevantfor:ae isaac jonasschmidt nadymmallek shailyverma year2025}, pages = {53:1–53:21}, title = {A Parameterized Study of Secluded Structures in Directed Graphs}, year = 2025 }

2023 [ nach oben ]

Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, Ziena Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded TreewidthSymposium Theory of Computing (STOC) 2023: 1325–1334
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-\(r\) graph, there exists a (fractional) multicommodity flow of value \(f\), and a multicut of capacity \(c\) such that \(f leq c leq \mathcal{O(\ln(r + 1)) \cdot f \) . It is well known that the multiflow-multicut gap on an \(r\)-vertex (constant degree) expander graph can be \(\Omega(ln r)\), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time \( \mathcal{O(ln(r + 1))\)-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.
@inproceedings{friedrich2023approximate, abstract = {We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-\(r\) graph, there exists a (fractional) multicommodity flow of value \(f\), and a multicut of capacity \(c\) such that \(f \leq c \leq \mathcal{O}(\ln(r + 1)) \cdot f \) . It is well known that the multiflow-multicut gap on an \(r\)-vertex (constant degree) expander graph can be \(\Omega(ln r)\), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time \( \mathcal{O}(ln(r + 1))\)-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.}, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, booktitle = {Symposium Theory of Computing (STOC)}, keywords = {davisissac nadymmallek nikhilkumar stoc tobiasfriedrich year2023 zienazeif}, pages = {1325–1334}, title = {Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth}, year = 2023 }

2022 [ nach oben ]

Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, Ziena A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2022: 55:1–55:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.
@inproceedings{friedrich2022primaldual, abstract = {We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.}, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, booktitle = {Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, keywords = {approx davisissac nadymmallek nikhilkumar tobiasfriedrich year2022 zienazeif}, pages = {55:1–55:18}, title = {A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs}, year = 2022 }