Matthias Mnich
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Matthias Mnich has a total of 173 co-authors. Here are the top co-authors by number of shared publications:
- Danny Hermelin
Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
9 shared publications - Dušan Knop
Czech Technical University in Prague
5 shared publications - Erik Jan van Leeuwen
Max-Planck-Institut für Informatik Saarland Informatics Campus Saarbrücken Germany
4 shared publications Gregory Gutin
Department of Computer Science Royal Holloway University of London Egham TW20 0EX Surrey UK
4 shared publications- Martin Koutecký
Computer Science Institute, Charles University, Prague, Czech Republic
4 shared publications Saket Saurabh
4 shared publications
Latest Publications
- Open Access
- 17 October 2026
- Published by International Union of Crystallography (IUCr) in Journal of Applied Crystallography
- Vol. 59 (6)
Iterative phase retrieval in macromolecular crystal diffraction using the gradients of intensities
Iterative phase retrieval (IPR) offers a model-independent route to crystallographic structure determination but is fundamentally limited by the sampling of the diffraction pattern at Bragg positions. Consequently, conventional IPR methods typically rely on a high solvent fraction (>70%) to sufficiently constrain the solution, a condition met by only a small fraction of protein crystals. This work investigates a magnitude-and-gradient IPR algorithm that overcomes this undersampling barrier by exploiting the local intensity gradients ∇ I ( q ) observable in the diffraction patterns of finite crystals. By incorporating the gradients of the molecular transform alongside Bragg intensities, the phase problem is converted from an underdetermined system of equations to one that is overdetermined by a factor of two. Tests on simulated diffraction data for proteins in space group P 1 demonstrate that the algorithm successfully reconstructs electron densities across a wide range of solvent fractions, including densely packed crystals where standard algorithms fail. Furthermore, the approach proves robust under experimentally relevant conditions, tolerating significant Poissonian noise and the loss of low-resolution terms due to a beamstop when coupled with approximate real-space support constraints. These results indicate that leveraging the fine structure of Bragg peaks at coherent X-ray sources can significantly extend the applicability of ab initio phasing.
- 17 October 2026
- Published by International Union of Crystallography (IUCr) in Journal of Applied Crystallography
- Vol. 59 (6)
Open AccessIterative phase retrieval in macromolecular crystal diffraction using the gradients of intensities
Iterative phase retrieval (IPR) offers a model-independent route to crystallographic structure determination but is fundamentally limited by the sampling of the diffraction pattern at Bragg positions. Consequently, conventional IPR methods typically rely on a high solvent fraction (>70%) to sufficiently constrain the solution, a condition met by only a small fraction of protein crystals. This work investigates a magnitude-and-gradient IPR algorithm that overcomes this undersampling barrier by exploiting the local intensity gradients ∇ I ( q ) observable in the diffraction patterns of finite crystals. By incorporating the gradients of the molecular transform alongside Bragg intensities, the phase problem is converted from an underdetermined system of equations to one that is overdetermined by a factor of two. Tests on simulated diffraction data for proteins in space group P 1 demonstrate that the algorithm successfully reconstructs electron densities across a wide range of solvent fractions, including densely packed crystals where standard algorithms fail. Furthermore, the approach proves robust under experimentally relevant conditions, tolerating significant Poissonian noise and the loss of low-resolution terms due to a beamstop when coupled with approximate real-space support constraints. These results indicate that leveraging the fine structure of Bragg peaks at coherent X-ray sources can significantly extend the applicability of ab initio phasing.
- Open Access
- 18 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms that achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n -vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, • Independent Set and Dominating Set can be solved in time \(2^{\mathcal {O}(dk)}\cdot n^{\mathcal {O}(1)} \) using \(\mathcal {O}(dk\log n) \) space; • Max Cut can be solved in time \(n^{\mathcal {O}(dk)} \) using \(\mathcal {O}(dk\log n) \) space. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence , which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial..- 18 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Open AccessSpace-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms that achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n -vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, • Independent Set and Dominating Set can be solved in time \(2^{\mathcal {O}(dk)}\cdot n^{\mathcal {O}(1)} \) using \(\mathcal {O}(dk\log n) \) space; • Max Cut can be solved in time \(n^{\mathcal {O}(dk)} \) using \(\mathcal {O}(dk\log n) \) space. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence , which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.. - Open Access
Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
We study the problem of partitioning a set of $n$ objects in a metric space into $k$ clusters $V_1,\dots,V_k$. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the $\ell_p$-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in~$V_i$, which may serve as a proxy for the cost of traversing all objects in the cluster, but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This setting has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett.}, 2004) for the setting of minimizing the weight of the largest cluster (i.e., using $\ell_\infty$) as Min-Max Tree Cover, for which they gave a constant-factor approximation. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. For this setting also we are able to give a polynomial time algorithm computing a constant factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single $\ell_p$ norm for the objective.Open AccessApproximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
We study the problem of partitioning a set of $n$ objects in a metric space into $k$ clusters $V_1,\dots,V_k$. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the $\ell_p$-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in~$V_i$, which may serve as a proxy for the cost of traversing all objects in the cluster, but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This setting has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett.}, 2004) for the setting of minimizing the weight of the largest cluster (i.e., using $\ell_\infty$) as Min-Max Tree Cover, for which they gave a constant-factor approximation. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. For this setting also we are able to give a polynomial time algorithm computing a constant factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single $\ell_p$ norm for the objective. - Open Access
- 22 October 2024
- Published by Springer Nature in Journal of Scheduling
- Vol. 27 (6) , 545-556
Serial batching to minimize the weighted number of tardy jobs
The $$1\vert \text {s-batch}(\infty ),r_j\vert \sum w_jU_j$$ scheduling problem takes as input a batch setup time $$\Delta $$ and a set of n jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79–86, 1994); as a wide generalization of Knapsack, it is $$\textsf{NP}$$ -hard. In this work, we provide a multivariate complexity analysis of the $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and $$\textsf{W}[1]$$ -hard problems, for parameter combinations of (i) $$\#p$$ = number of distinct processing times, (ii) $$\#w$$ = number of distinct weights, (iii) $$\#d$$ = number of distinct due dates, (iv) $$\#r$$ = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271–287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ is $$\textsf{W}[1]$$ -hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ is fixed-parameter tractable parameterized by $$\#d + \#p + \#r$$ , and parameterized by $$\#d + \#w$$ if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b.- 22 October 2024
- Published by Springer Nature in Journal of Scheduling
- Vol. 27 (6) , 545-556
Open AccessSerial batching to minimize the weighted number of tardy jobs
The $$1\vert \text {s-batch}(\infty ),r_j\vert \sum w_jU_j$$ scheduling problem takes as input a batch setup time $$\Delta $$ and a set of n jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79–86, 1994); as a wide generalization of Knapsack, it is $$\textsf{NP}$$ -hard. In this work, we provide a multivariate complexity analysis of the $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and $$\textsf{W}[1]$$ -hard problems, for parameter combinations of (i) $$\#p$$ = number of distinct processing times, (ii) $$\#w$$ = number of distinct weights, (iii) $$\#d$$ = number of distinct due dates, (iv) $$\#r$$ = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271–287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ is $$\textsf{W}[1]$$ -hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that $$1\vert \text {s-batch}(\infty ), r_j\vert \sum w_jU_j$$ is fixed-parameter tractable parameterized by $$\#d + \#p + \#r$$ , and parameterized by $$\#d + \#w$$ if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b. - Open Access
Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
We study the fundamental scheduling problem $1\mid r_j\mid\sum w_j U_j$: schedule a set of $n$ jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem $1\mid r_j\mid\sum w_j U_j$ generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. [Annals of Operations Research, 2021] from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of $1\mid r_j\mid\sum w_j U_j$ in terms of four key problem parameters: the number $p_\#$ of processing times, the number $w_\#$ of weights, the number $d_\#$ of due dates, and the number $r_\#$ of release dates of the jobs. $1\mid r_j\mid\sum w_j U_j$ is known to be weakly para-NP-hard even if $w_\#+d_\#+r_\#$ is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) W[1]-hardness parameterized by $p_\#$ or $w_\#$ even if $r_\#$ is constant. Algorithmically, we show that $1\mid r_j\mid\sum w_j U_j$ is fixed-parameter tractable parameterized by $p_\#$ combined with any two of the remaining three parameters $w_\#$, $d_\#$, and $r_\#$. We further provide pseudo-polynomial XP-time algorithms for parameter $r_\#$ and $d_\#$. To complement these algorithms, we show that $1\mid r_j\mid\sum w_j U_j$ is (strongly) W[1]-hard when parameterized by $d_\#+r_\#$ even if $w_\#$ is constant. Our results provide a nearly complete picture of the complexity of $1\mid r_j\mid\sum w_j U_j$ for $p_\#$, $w_\#$, $d_\#$, and $r_\#$ as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem $1\mid\mid\sum w_j U_j$ without release dates.Open AccessSingle-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
We study the fundamental scheduling problem $1\mid r_j\mid\sum w_j U_j$: schedule a set of $n$ jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem $1\mid r_j\mid\sum w_j U_j$ generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. [Annals of Operations Research, 2021] from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of $1\mid r_j\mid\sum w_j U_j$ in terms of four key problem parameters: the number $p_\#$ of processing times, the number $w_\#$ of weights, the number $d_\#$ of due dates, and the number $r_\#$ of release dates of the jobs. $1\mid r_j\mid\sum w_j U_j$ is known to be weakly para-NP-hard even if $w_\#+d_\#+r_\#$ is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) W[1]-hardness parameterized by $p_\#$ or $w_\#$ even if $r_\#$ is constant. Algorithmically, we show that $1\mid r_j\mid\sum w_j U_j$ is fixed-parameter tractable parameterized by $p_\#$ combined with any two of the remaining three parameters $w_\#$, $d_\#$, and $r_\#$. We further provide pseudo-polynomial XP-time algorithms for parameter $r_\#$ and $d_\#$. To complement these algorithms, we show that $1\mid r_j\mid\sum w_j U_j$ is (strongly) W[1]-hard when parameterized by $d_\#+r_\#$ even if $w_\#$ is constant. Our results provide a nearly complete picture of the complexity of $1\mid r_j\mid\sum w_j U_j$ for $p_\#$, $w_\#$, $d_\#$, and $r_\#$ as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem $1\mid\mid\sum w_j U_j$ without release dates. - Open Access
- 1 August 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 3, 1856-1864
MS-DPPs: Multi-Source Determinantal Point Processes for Contextual Diversity Refinement of Composite Attributes in Text to Image Retrieval
Result diversification (RD) is a crucial technique in Text-to-Image Retrieval for enhancing the efficiency of a practical application. Conventional methods focus solely on increasing the diversity metric of image appearances. However, the diversity metric and its desired value vary depending on the application, which limits the applications of RD. This paper proposes a novel task called CDR-CA (Contextual Diversity Refinement of Composite Attributes). CDR-CA aims to refine the diversities of multiple attributes, according to the application's context. To address this task, we propose Multi-Source DPPs, a simple yet strong baseline that extends the Determinantal Point Process (DPP) to multi-sources. We model MS-DPP as a single DPP model with a unified similarity matrix based on a manifold representation. We also introduce Tangent Normalization to reflect contexts. Extensive experiments demonstrate the effectiveness of the proposed method.
- 1 August 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 3, 1856-1864
Open AccessMS-DPPs: Multi-Source Determinantal Point Processes for Contextual Diversity Refinement of Composite Attributes in Text to Image Retrieval
Result diversification (RD) is a crucial technique in Text-to-Image Retrieval for enhancing the efficiency of a practical application. Conventional methods focus solely on increasing the diversity metric of image appearances. However, the diversity metric and its desired value vary depending on the application, which limits the applications of RD. This paper proposes a novel task called CDR-CA (Contextual Diversity Refinement of Composite Attributes). CDR-CA aims to refine the diversities of multiple attributes, according to the application's context. To address this task, we propose Multi-Source DPPs, a simple yet strong baseline that extends the Determinantal Point Process (DPP) to multi-sources. We model MS-DPP as a single DPP model with a unified similarity matrix based on a manifold representation. We also introduce Tangent Normalization to reflect contexts. Extensive experiments demonstrate the effectiveness of the proposed method.
- Open Access
A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
We present a new $(\frac32+\frac1{\mathrm{e}})$-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately $1.868$ holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of $\frac52$ for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction.Open AccessA $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
We present a new $(\frac32+\frac1{\mathrm{e}})$-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately $1.868$ holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of $\frac52$ for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction. - Open Access
A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values, a research area which was pioneered by Venkatesh Raman. Those problems seek, for a given graph $G$, a solution whose value is at least $g(G)+k$ or at most $g(G)-k$, where $g(G)$ is a guarantee on the value that any solution on $G$ takes. The goal is to design algorithms which find such solution in time whose complexity in $k$ is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems.Open AccessA Survey on Graph Problems Parameterized Above and Below Guaranteed Values
We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values, a research area which was pioneered by Venkatesh Raman. Those problems seek, for a given graph $G$, a solution whose value is at least $g(G)+k$ or at most $g(G)-k$, where $g(G)$ is a guarantee on the value that any solution on $G$ takes. The goal is to design algorithms which find such solution in time whose complexity in $k$ is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems. - 7 February 2024
- Published by Springer Nature
- p. 82-95
New Support Size Bounds and Proximity Bounds for Integer Linear Programming
- 7 February 2024
- Published by Springer Nature
- p. 82-95
New Support Size Bounds and Proximity Bounds for Integer Linear Programming
- Open Access
- 22 January 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (1) , 1-20
Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter
The fundamental Sparsest Cut problem takes as input a graph G together with edge capacities and demands and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For n -vertex graphs G of treewidth k , Chlamtáč, Krauthgamer, and Raghavendra (APPROX’10) presented an algorithm that yields a factor- \(2^{2^k}\) approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . Later, Gupta, Talwar, and Witmer (STOC’13) showed how to obtain a 2-approximation algorithm with a blown-up runtime of \(n^{O(k)}\) . An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-2 approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . In this article, we make significant progress towards this goal via the following results: (i) A factor- \(O(k^2)\) approximation that runs in time \(2^{O(k)} \cdot n^{O(1)}\) , directly improving the work of Chlamtáč et al. while keeping the runtime single-exponential in k . (ii) For any \(\varepsilon \in (0,1]\) , a factor- \(O(1/\varepsilon ^2)\) approximation whose runtime is \(2^{O(k^{1+\varepsilon }/\varepsilon)} \cdot n^{O(1)}\) , implying a constant-factor approximation whose runtime is nearly single-exponential in k and a factor- \(O(\log ^2 k)\) approximation in time \(k^{O(k)} \cdot n^{O(1)}\) . Key to these results is a new measure of a tree decomposition that we call combinatorial diameter , which may be of independent interest.- 22 January 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (1) , 1-20
Open AccessApproximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter
The fundamental Sparsest Cut problem takes as input a graph G together with edge capacities and demands and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For n -vertex graphs G of treewidth k , Chlamtáč, Krauthgamer, and Raghavendra (APPROX’10) presented an algorithm that yields a factor- \(2^{2^k}\) approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . Later, Gupta, Talwar, and Witmer (STOC’13) showed how to obtain a 2-approximation algorithm with a blown-up runtime of \(n^{O(k)}\) . An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-2 approximation in time \(2^{O(k)} \cdot n^{O(1)}\) . In this article, we make significant progress towards this goal via the following results: (i) A factor- \(O(k^2)\) approximation that runs in time \(2^{O(k)} \cdot n^{O(1)}\) , directly improving the work of Chlamtáč et al. while keeping the runtime single-exponential in k . (ii) For any \(\varepsilon \in (0,1]\) , a factor- \(O(1/\varepsilon ^2)\) approximation whose runtime is \(2^{O(k^{1+\varepsilon }/\varepsilon)} \cdot n^{O(1)}\) , implying a constant-factor approximation whose runtime is nearly single-exponential in k and a factor- \(O(\log ^2 k)\) approximation in time \(k^{O(k)} \cdot n^{O(1)}\) . Key to these results is a new measure of a tree decomposition that we call combinatorial diameter , which may be of independent interest.