publications | Barış Can Esmer

2024

SODA 2024
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations

Barış Can Esmer, Ariel Kulik, Dániel Marx, and 2 more authors

In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , Jan 2024

Abs arXiv Bib

The goal of this paper is to understand how exponential-time approximation algorithms can be obtained from existing polynomial-time approximation algorithms, existing parameterized exact algorithms, and existing parameterized approximation algorithms. More formally, we consider a monotone subset minimization problem over a universe of size n (e.g., VERTEX COVER or FEEDBACK VERTEX Set). We have access to an algorithm that finds an α-approximate solution in time ck ⋅ nO(1) if a solution of size k exists (and more generally, an extension algorithm that can approximate in a similar way if a set can be extended to a solution with k further elements). Our goal is to obtain a dn ⋅ nO(1) time β-approximation algorithm for the problem with d as small as possible. That is, for every fixed α,c,β ≥ 1, we would like to determine the smallest possible d that can be achieved in a model where our problem-specific knowledge is limited to checking the feasibility of a solution and invoking the α-approximate extension algorithm. Our results completely resolve this question: 1. For every fixed α, c, β ≥ 1, a simple algorithm (“approximate monotone local search”) achieves the optimum value of d. 2. Given α, c, β ≥ 1, we can efficiently compute the optimum d up to any precision \varepsilon > 0. Our technique gives novel results for a wide range of problems including FEEDBACK VERTEX Set, DIRECTED Feedback Vertex Set, Odd Cycle Traversal and Partial Vertex Cover. The monotone local search algorithm we use is a simple adaptation of [Fomin et al., J. ACM 2019, Esmer et al., ESA 2022, Gaspers and Lee, ICALP 2017]. Still, attaining the above results required us to frame the result in a different way, and overcome a major technical challenge. First, we introduce an oracle based computational model which allows for a simple derivation of lower bounds that, unexpectedly, show that the running time of the monotone local search algorithm is optimal. Second, while it easy to express the running time of the monotone local search algorithm in various forms, it is unclear how to actually numerically evaluate it for given values of α, β and c. We show how the running time of the algorithm can be evaluated via a convex analysis of a continuous max-min optimization problem, overcoming the limitations of previous approaches to the α = β case [Fomin et al., J. ACM 2019, Esmer et al., ESA 2022, Gaspers and Lee, ICALP 2017]. * The full version of the paper can be accessed at https://arxiv.org/abs/2306.15331. Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.
@incollection{canesmerOptimallyRepurposingExisting2024, title = {Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations}, booktitle = {Proceedings of the 2024 {{Annual ACM-SIAM Symposium}} on {{Discrete Algorithms}} ({{SODA}})}, author = {Can Esmer, Bar{\i}{\c s} and Kulik, Ariel and Marx, D{\'a}niel and Neuen, Daniel and Sharma, Roohani}, year = {2024}, bibtex_show = true, month = jan, series = {Proceedings}, pages = {314--345}, publisher = {{Society for Industrial and Applied Mathematics}}, doi = {10.1137/1.9781611977912.13}, urldate = {2024-03-27}, }
Algorithmica
Computing Generalized Convolutions Faster Than Brute Force

Barış Can Esmer, Ariel Kulik, Dániel Marx, and 2 more authors

Algorithmica, Jan 2024

Abs arXiv Bib

In this paper, we consider a general notion of convolution. Let \\D\\be a finite domain and let \\D^n\\be the set of n-length vectors (tuples) of \\D\\. Let \\f :D}times D}rightarrow D\\be a function and let \{}oplus _f\\be a coordinate-wise application of f. The \\f\\-Convolution of two functions \\g,h :D^n }rightarrow }{-M,}ldots ,M}}\\is \{}begin{aligned} (g }mathbin {}circledast _{f}}h)(}textbf{v}) {:}{=}}sum _{}begin{array}{c} }textbf{v}_g,}textbf{v}_h }in D^n}} }text {s.t. } }textbf{v}= }textbf{v}_g }oplus _f }textbf{v}_h }end{array}} g(}textbf{v}_g) }cdot h(}textbf{v}_h) }end{aligned}\\(g⊛fh)(v):=∑vg,vh∈Dns.t.v=vg⊕fvhg(vg)⋅h(vh)for every \{}textbf{v}}in D^n\\. This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function f and domain \\D\\we can compute \\f\\-Convolution via brute-force enumeration in \{}widetilde{{}mathcal {O}}}(\textbarD\textbar^{2n} }cdot }textrm{polylog}(M))\\time. Our main result is an improvement over this naive algorithm. We show that \\f\\-Convolution can be computed exactly in \{}widetilde{{}mathcal {O}}}( (c }cdot \textbarD\textbar^2)^{n} }cdot }textrm{polylog}(M))\\for constant \\c {:}{=}3/4\\when \\D\\has even cardinality. Our main observation is that a cyclic partition of a function \\f :D}times D}rightarrow D\\can be used to speed up the computation of \\f\\-Convolution, and we show that an appropriate cyclic partition exists for every f. Furthermore, we demonstrate that a single entry of the \\f\\-Convolution can be computed more efficiently. In this variant, we are given two functions \\g,h :D^n }rightarrow }{-M,}ldots ,M}}\\alongside with a vector \{}textbf{v}}in D^n\\and the task of the \\f\\-Query problem is to compute integer \\(g }mathbin {}circledast _{f}}h)(}textbf{v})\\. This is a generalization of the well-known Orthogonal Vectors problem. We show that \\f\\-Query can be computed in \{}widetilde{{}mathcal {O}}}(\textbarD\textbar^{}frac{}omega }{2} n} }cdot }textrm{polylog}(M))\\time, where \{}omega }in [2,2.372)\\is the exponent of currently fastest matrix multiplication algorithm.
@article{esmerComputingGeneralizedConvolutions2024, title = {Computing {{Generalized Convolutions Faster Than Brute Force}}}, author = {Esmer, Bar{\i}{\c s} Can and Kulik, Ariel and Marx, D{\'a}niel and Schepper, Philipp and W{\k e}grzycki, Karol}, year = {2024}, month = jan, journal = {Algorithmica}, volume = {86}, number = {1}, pages = {334--366}, issn = {1432-0541}, doi = {10.1007/s00453-023-01176-2}, selected = true, bibtex_show = true, urldate = {2024-03-27}, langid = {english}, keywords = {Algorithm design techniques,Fast Fourier Transform,Fast Subset Convolution,Generalized Convolution,Orthogonal Vectors,Parameterized complexity and exact algorithms,Theory of computation} }
arXiv
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness

Barış Can Esmer, Jacob Focke, Dániel Marx, and 1 more author

Feb 2024

Abs Bib

It is known for many algorithmic problems that if a tree decomposition of width \t is given in the input, then the problem can be solved with exponential dependence on \t\. A line of research by Lokshtanov, Marx, and Saurabh [SODA 2011] produced lower bounds showing that in many cases known algorithms achieve the best possible exponential dependence on \t assuming the SETH. The main message of our paper is showing that the same lower bounds can be obtained in a more restricted setting: a graph consisting of a block of \t vertices connected to components of constant size already has the same hardness as a general tree decomposition of width \t\. Formally, a \(}sigma,}delta)\-hub is a set \Q of vertices such that every component of \Q has size at most {}sigma and is adjacent to at most {}delta vertices of \Q\. {}bullet For every {}epsilon> 0 there are {}sigma,}delta> 0 such that Independent Set/Vertex Cover cannot be solved in time \(2-}epsilon)^p}cdot n even if a \(}sigma,}delta)\-hub of size \p is given in the input, assuming the SETH. This matches the earlier tight lower bounds parameterized by the width of the tree decomposition. Similar tight bounds are obtained for Odd Cycle Transversal, Max Cut, \q\-Coloring, and edge/vertex deletions versions of \q\-Coloring. {}bullet For every {}epsilon>0 there are {}sigma,}delta> 0 such that Triangle-Partition cannot be solved in time \(2-}epsilon)^p}cdot n even if a \(}sigma,}delta)\-hub of size \p is given in the input, assuming the Set Cover Conjecture (SCC). In fact, we prove that this statement is equivalent to the SCC, thus it is unlikely that this could be proved assuming the SETH. {}bullet For Dominating Set, we can prove a non-tight lower bound ruling out \(2-}epsilon)^p}cdot n^{O(1)} algorithms, assuming either the SETH or the SCC, but this does not match the \3^p}cdot n^{O(1)} upper bound.
@misc{esmerFundamentalProblemsBoundedTreewidth2024, title = {Fundamental {{Problems}} on {{Bounded-Treewidth Graphs}}: {{The Real Source}} of {{Hardness}}}, shorttitle = {Fundamental {{Problems}} on {{Bounded-Treewidth Graphs}}}, author = {Esmer, Bar{\i}{\c s} Can and Focke, Jacob and Marx, D{\'a}niel and Rz{\k a}{\.z}ewski, Pawe{\l}}, year = {2024}, bibtex_show = true, month = feb, number = {arXiv:2402.07331}, eprint = {2402.07331}, primaryclass = {cs}, publisher = {arXiv}, urldate = {2024-03-27}, archiveprefix = {arxiv}, keywords = {Computer Science - Computational Complexity,Computer Science - Data Structures and Algorithms} }
arXiv
List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs

Barış Can Esmer, Jacob Focke, Dániel Marx, and 1 more author

Feb 2024

Abs Bib

The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict the problem to bounded-treewidth graphs. For a fixed \H the input of the optimization problem LHomVD(\H\) is a graph \G with lists Ł(v) and the task is to find a set \X of vertices having minimum size such that $G-X,L) has a list homomorphism to \H\. We define analogously the edge-deletion variant LHomED(\H$. This expressive family of problems includes members that are essentially equivalent to fundamental problems such as Vertex Cover, Max Cut, Odd Cycle Transversal, and Edge/Vertex Multiway Cut. For both variants, we first characterize those graphs \H that make the problem polynomial-time solvable and show that the problem is NP-hard for every other fixed \H\. Second, as our main result, we determine for every graph \H for which the problem is NP-hard, the smallest possible constant \c_H such that the problem can be solved in time \c^t_H}cdot n^{O(1)} if a tree decomposition of \G having width \t is given in the input.Let \i(H) be the maximum size of a set of vertices in \H that have pairwise incomparable neighborhoods. For the vertex-deletion variant LHomVD(\H\), we show that the smallest possible constant is \i(H)+1 for every \H\. The situation is more complex for the edge-deletion version. For every \H one can solve LHomED(\H\) in time \i(H)^t}cdot n^{O(1)} if a tree decomposition of width \t is given. However, the existence of a specific type of decomposition of \H shows that there are graphs \H where LHomED(\H\) can be solved significantly more efficiently and the best possible constant can be arbitrarily smaller than \i(H)\. Nevertheless, we determine this best possible constant and (assuming the SETH) prove tight bounds for every fixed \H\.
@misc{esmerListHomomorphismsDeleting2024, title = {List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs}, shorttitle = {List Homomorphisms by Deleting Edges and Vertices}, author = {Esmer, Bar{\i}{\c s} Can and Focke, Jacob and Marx, D{\'a}niel and Rz{\k a}{\.z}ewski, Pawe{\l}}, year = {2024}, bibtex_show = true, month = feb, number = {arXiv:2210.10677}, eprint = {2210.10677}, primaryclass = {cs}, publisher = {arXiv}, urldate = {2024-03-27}, archiveprefix = {arxiv}, keywords = {Computer Science - Computational Complexity,Computer Science - Data Structures and Algorithms} }

2023

IPEC 2023
Approximate Monotone Local Search for Weighted Problems

Barış Can Esmer, Ariel Kulik, Dániel Marx, and 2 more authors

In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) , Feb 2023

Abs arXiv Bib

In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting. More formally, we consider monotone subset minimization problems over a weighted universe of size n (e.g., Vertex Cover, d-Hitting Set and Feedback Vertex Set). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most α ⋅ W (and of arbitrary cardinality) in time c^k ⋅ n^{O(1)} where W is the minimum weight of a solution of cardinality at most k. In the unweighted setting, Esmer et al. determine the smallest value d for which a β-approximation algorithm running in time d^n ⋅ n^{O(1)} can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: for every fixed \varepsilon > 0 we obtain a β-approximation algorithm running in time O((d+\varepsilon)^n), for the same d as in the unweighted setting. Similarly, we also extend a β-approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time β-approximation algorithms that are better than brute force for a variety of problems including Weighted Vertex Cover, Weighted d-Hitting Set, Weighted Feedback Vertex Set and Weighted Multicut.
@inproceedings{esmerApproximateMonotoneLocal2023, title = {Approximate {{Monotone Local Search}} for {{Weighted Problems}}}, bibtex_show = true, author = {Esmer, Bar{\i}{\c s} Can and Kulik, Ariel and Marx, D{\'a}niel and Neuen, Daniel and Sharma, Roohani}, year = {2023}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/LIPIcs.IPEC.2023.17}, urldate = {2024-03-27}, copyright = {https://creativecommons.org/licenses/by/4.0/legalcode}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, langid = {english} }

2022

ESA 2022

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search

Bariş Can Esmer, Ariel Kulik, Dániel Marx, and 2 more authors

In 30th Annual European Symposium on Algorithms (ESA 2022) , Feb 2022

arXiv Bib

@inproceedings{EsmerESA22,
  selected = true,
  bibtex_show = true,
  address = {Berlin/Potsdam, Germany},
  author = {Esmer, Bari{\c s} Can and Kulik, Ariel and Marx, D{\'a}niel and Neuen, Daniel and Sharma, Roohani},
  booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
  doi = {10.4230/LIPIcs.ESA.2022.50},
  editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  eid = {50},
  isbn = {978-3-95977-247-1},
  issn = {1868-8969},
  language = {eng},
  marginalmark = {$\bullet$},
  pages = {1--19},
  publisher = {Schloss Dagstuhl},
  series = {Leibniz International Proceedings in Informatics},
  title = {Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search},
  url = {urn:nbn:de:0030-drops-169887; https://drops.dagstuhl.de/opus/volltexte/2022/16988/},
  volume = {244},
  year = {2022}
}

ISIT 2022
On (1 + ε)-Approximate Block Sparse Recovery

Barış Can Esmer, and Vasileios Nakos

In 2022 IEEE International Symposium on Information Theory (ISIT) , Jun 2022

Abs Bib

Learning approximately block sparse vectors using a small number of linear measurements is a standard task in the sparse recovery/compressed sensing literature. Schemes achieving a constant factor approximation are long known, e.g. using model-based RIP. We give a new scheme achieving (1+ ε) approximation, which runs in near linear time in the length of the vector and is likely to be optimal up to constant factors. As an intriguing side result, we obtain the simplest known scheme measurement-optimal \ell2/\ell2 sparse recovery scheme recorded in the literature. The main component of our algorithm is a subtle variant of the classic COUNTSKETCH data structure where the random signs are substituted by Gaussians and the number of repetitions (rows) is tuned to smaller than usual.
@inproceedings{esmerApproximateBlockSparse2022, title = {On (1 + {$\epsilon$})-{{Approximate Block Sparse Recovery}}}, booktitle = {2022 {{IEEE International Symposium}} on {{Information Theory}} ({{ISIT}})}, author = {Esmer, Bar{\i}{\c s} Can and Nakos, Vasileios}, year = {2022}, bibtex_show = true, month = jun, pages = {1815--1820}, issn = {2157-8117}, doi = {10.1109/ISIT50566.2022.9834705}, urldate = {2024-03-27}, keywords = {Approximation algorithms,Data structures,Information theory,model based sparse recovery,Sensors,sparse recovery,Standards,Task analysis} }