4 Search Results for "Etscheid, Michael"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.66
A Parameterized-Complexity Framework for Finding Local Optima

Authors: Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood. The traditional frameworks, PLS and the standard algorithm problem, introduced by Johnson, Papadimitriou, and Yannakakis (1988) fail to capture the methodology of local search algorithms: PLS is concerned with finding a local optimum and not with using local search, while the standard algorithm problem restricts each improvement step to follow a fixed pivoting rule. In this work, we introduce a novel formulation of local search which provides a middle ground between these models. In particular, the task is to output not only a local optimum but also a chain of local improvements leading to it. With this framework, we aim to capture the challenge in designing a good pivoting rule. Especially, when combined with the parameterized complexity paradigm, it enables both strong lower bounds and meaningful tractability results. Unlike previous works that combined parameterized complexity with local search, our framework targets the whole task of finding a local optimum and not only a single improvement step. Focusing on two representative meta-problems - Subset Weight Optimization Problem with the c-swap neighborhood and Weighted Circuit with the flip neighborhood - we establish fixed-parameter tractability results related to the number of distinct weights, while ruling out an analogous result when parameterizing by the distance to the nearest optimum via a new type of reduction.
Cite as

Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz. A Parameterized-Complexity Framework for Finding Local Optima. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.ITCS.2026.66,
  author =	{Ganian, Robert and Hoang, Hung P. and Komusiewicz, Christian and Morawietz, Nils},
  title =	{{A Parameterized-Complexity Framework for Finding Local Optima}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{66:1--66:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.66},
  URN =		{urn:nbn:de:0030-drops-253532},
  doi =		{10.4230/LIPIcs.ITCS.2026.66},
  annote =	{Keywords: Local Search, Parameterized Complexity, PLS}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.16
Designing Compact ILPs via Fast Witness Verification

Authors: Michał Włodarczyk

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preprocessing for problems without polynomial kernels, still aiming at producing instances that are easily solvable in practice. Specifically, we ask for which parameterized problems an instance (I,k) can be reduced in polynomial time to an integer linear program (ILP) with poly(k) constraints. We show that this property coincides with the parameterized complexity class WK[1], previously studied in the context of Turing kernelization lower bounds. In turn, the class WK[1] enjoys an elegant characterization in terms of witness verification protocols: a yes-instance should admit a witness of size poly(k) that can be verified in time poly(k). By combining known data structures with new ideas, we design such protocols for several problems, such as r-Way Cut, Vertex Multiway Cut, Steiner Tree, and Minimum Common String Partition, thus showing that they can be modeled by compact ILPs. We also present explicit ILP and MILP formulations for Weighted Vertex Cover on graphs with small (unweighted) vertex cover number. We believe that these results will provide a background for a systematic study of ILP-oriented preprocessing procedures for parameterized problems.
Cite as

Michał Włodarczyk. Designing Compact ILPs via Fast Witness Verification. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.IPEC.2025.16,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Designing Compact ILPs via Fast Witness Verification}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.16},
  URN =		{urn:nbn:de:0030-drops-251481},
  doi =		{10.4230/LIPIcs.IPEC.2025.16},
  annote =	{Keywords: integer programming, kernelization, nondeterminism, multiway cut}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.15
When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in ℝ^d (d ≥ 1), or equivalently, distance spaces that can be isometrically embedded in ℝ^d. In this work, we investigate whether a distance space can be isometrically embedded in ℝ^d after applying a limited number of modifications. Specifically, we focus on two types of modifications: outlier deletion (removing points) and distance modification (adjusting distances between points). The central problem, Euclidean Embedding Editing, asks whether an input distance space on n points can be transformed, using at most k modifications, into a space that is isometrically embeddable in ℝ^d. We present several fixed-parameter tractable (FPT) and approximation algorithms for this problem. Our first result is an algorithm that solves Euclidean Embedding Editing in time (dk)^𝒪(d+k) + n^𝒪(1). The core subroutine of this algorithm, which is of independent interest, is a polynomial-time method for compressing the input distance space into an equivalent instance of Euclidean Embedding Editing with 𝒪((dk)²) points. For the special but important case of Euclidean Embedding Editing where only outlier deletions are allowed, we improve the parameter dependence of the FPT algorithm and obtain a running time of min{(d+3)^k, 2^{d+k}} ⋅ n^𝒪(1). Additionally, we provide an FPT-approximation algorithm for this problem, which outputs a set of at most 2 ⋅ Opt outliers in time 2^d ⋅ n^{𝒪(1)}. This 2-approximation algorithm improves upon the previous (3+ε)-approximation algorithm by Sidiropoulos, Wang, and Wang [SODA '17]. Furthermore, we complement our algorithms with hardness results motivating our choice of parameterizations.
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan, and Saket Saurabh. When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.SoCG.2025.15,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Ramanujan, M. S. and Saurabh, Saket},
  title =	{{When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.15},
  URN =		{urn:nbn:de:0030-drops-231672},
  doi =		{10.4230/LIPIcs.SoCG.2025.15},
  annote =	{Keywords: Parameterized Complexity, Euclidean Embedding, FPT-approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.31
Linear Kernels and Linear-Time Algorithms for Finding Large Cuts

Authors: Michael Etscheid and Matthias Mnich

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: * We show that an algorithm by Crowston et al. [ICALP 2012] for (Signed) Max-Cut Above Edwards-Erdos Bound can be implemented in such a way that it runs in linear time 8^k · O(m); this significantly improves the previous analysis with run time 8^k · O(n^4). * We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erdos Bound with O(k) vertices, improving a kernel with O(k^3) vertices by Crowston et al. [COCOON 2013]. * We improve all known kernels for strongly lambda-extendable properties parameterized above tight lower bound by Crowston et al. [FSTTCS 2013] from O(k^3) vertices to O(k) vertices. * As a consequence, Max Acyclic Subdigraph parameterized above Poljak-Turzik bound admits a kernel with O(k) vertices and can be solved in time 2^{O(k)} * n^{O(1)} ; this answers an open question by Crowston et al. [FSTTCS 2012]. All presented kernels can be computed in time O(km).
Cite as

Michael Etscheid and Matthias Mnich. Linear Kernels and Linear-Time Algorithms for Finding Large Cuts. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{etscheid_et_al:LIPIcs.ISAAC.2016.31,
  author =	{Etscheid, Michael and Mnich, Matthias},
  title =	{{Linear Kernels and Linear-Time Algorithms for Finding Large Cuts}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{31:1--31:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.31},
  URN =		{urn:nbn:de:0030-drops-68016},
  doi =		{10.4230/LIPIcs.ISAAC.2016.31},
  annote =	{Keywords: Max-Cut, fixed-parameter tractability, kernelization}
}
  • Refine by Type
  • 4 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2016

  • Refine by Author
  • 1 Bentert, Matthias
  • 1 Etscheid, Michael
  • 1 Fomin, Fedor V.
  • 1 Ganian, Robert
  • 1 Golovach, Petr A.
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 2 Parameterized Complexity
  • 2 kernelization
  • 1 Euclidean Embedding
  • 1 FPT-approximation
  • 1 Local Search
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact