19 Search Results for "Paschos, Vangelis Th."

Document
DOI: 10.4230/LIPIcs.SWAT.2026.4
Improved Bounds for Online TSP on the Half-Line

Authors: Júlia Baligács, Yann Disser, and Linda Thelen

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a 2-competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of 2.04. We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below 2. We introduce a second algorithm that beats the barrier of 2 by carefully modulating its speed, and prove a tight bound of 1.75 on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from 1.627 to 1.646.
Cite as

Júlia Baligács, Yann Disser, and Linda Thelen. Improved Bounds for Online TSP on the Half-Line. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.SWAT.2026.4,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Thelen, Linda},
  title =	{{Improved Bounds for Online TSP on the Half-Line}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.4},
  URN =		{urn:nbn:de:0030-drops-260402},
  doi =		{10.4230/LIPIcs.SWAT.2026.4},
  annote =	{Keywords: online algorithms, competitive analysis, server problems, online TSP}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.8
Binary k-Center with Missing Entries: Structure Leads to Tractability

Authors: Tobias Friedrich, Kirill Simonov, and Farehe Soheil

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

Abstract
k-Center clustering is a fundamental classification problem, where the task is to categorize the given collection of entities into k clusters and come up with a representative for each cluster, so that the maximum distance between an entity and its representative is minimized. In this work, we focus on the setting where the entities are represented by binary vectors with missing entries, which model incomplete categorical data. This version of the problem has wide applications, from predictive analytics to bioinformatics. Our main finding is that the problem, which is notoriously hard from the classical complexity viewpoint, becomes tractable as soon as the known entries are sparse and exhibit a certain structure. Formally, we show fixed-parameter tractable algorithms for the parameters vertex cover, fracture number, and treewidth of the row-column graph, which encodes the positions of the known entries of the matrix. Additionally, we tie the complexity of the 1-cluster variant of the problem, which is famous under the name Closest String, to the complexity of solving integer linear programs with few constraints. This implies, in particular, that improving upon the running times of our algorithms would lead to more efficient algorithms for integer linear programming in general.
Cite as

Tobias Friedrich, Kirill Simonov, and Farehe Soheil. Binary k-Center with Missing Entries: Structure Leads to Tractability. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:LIPIcs.IPEC.2025.8,
  author =	{Friedrich, Tobias and Simonov, Kirill and Soheil, Farehe},
  title =	{{Binary k-Center with Missing Entries: Structure Leads to Tractability}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{8:1--8:19},
  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.8},
  URN =		{urn:nbn:de:0030-drops-251403},
  doi =		{10.4230/LIPIcs.IPEC.2025.8},
  annote =	{Keywords: Clustering, Missing Entries, k-Center, Parameterized Algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.17
Treedepth Inapproximability and Exponential ETH Lower Bound

Authors: Édouard Bonnet, Daniel Neuen, and Marek Sokołowski

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

Abstract
Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a 2^{O(k²)} n-time exact algorithm and a polynomial-time O(OPT log^{3/2} OPT)-approximation algorithm, where the former algorithm returns an elimination forest of height k (witnessing that treedepth is at most k) for the n-vertex input graph G, or correctly reports that G has treedepth larger than k, and OPT is the actual value of the treedepth. On the complexity side, exactly computing treedepth is NP-complete, but the known reductions do not rule out a polynomial-time approximation scheme (PTAS), and under the Exponential Time Hypothesis (ETH) only exclude a running time of 2^o(√n) for exact algorithms. We show that 1.0003-approximating Treedepth is NP-hard, and that exactly computing the treedepth of an n-vertex graph requires time 2^Ω(n), unless the ETH fails. We further derive that there exist absolute constants δ, c > 0 such that any (1+δ)-approximation algorithm requires time 2^Ω(n/log^c n). We do so via a simple direct reduction from Satisfiability to Treedepth, inspired by a reduction recently designed for Treewidth [STOC '25].
Cite as

Édouard Bonnet, Daniel Neuen, and Marek Sokołowski. Treedepth Inapproximability and Exponential ETH Lower Bound. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2025.17,
  author =	{Bonnet, \'{E}douard and Neuen, Daniel and Soko{\l}owski, Marek},
  title =	{{Treedepth Inapproximability and Exponential ETH Lower Bound}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{17:1--17:10},
  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.17},
  URN =		{urn:nbn:de:0030-drops-251494},
  doi =		{10.4230/LIPIcs.IPEC.2025.17},
  annote =	{Keywords: treedepth, lower bounds, approximation}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.19
Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width

Authors: Narek Bojikian and Stefan Kratsch

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

Abstract
Recently, Bojikian and Kratsch [ICALP 2024] presented a novel approach to tackle connectivity problems parameterized by clique-width (cw), based on counting (modulo 2) the number of representations of partial solutions, while allowing for possibly multiple representations to exist for the same partial solution. Using this technique, they got a SETH-tight bound of 𝒪^*(3^{cw}) for the Steiner Tree problem, which was left open by Hegerfeld and Kratsch [ESA 2023]. We use the same technique to solve the Connected Odd Cycle Transversal problem in time 𝒪^*(12^{cw}). Moreover, we prove that our result is tight by providing a SETH-based lower bound excluding algorithms with running time 𝒪^*((12-ε)^{cw}). This answers another question of Hegerfeld and Kratsch [ESA 2023].
Cite as

Narek Bojikian and Stefan Kratsch. Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.IPEC.2025.19,
  author =	{Bojikian, Narek and Kratsch, Stefan},
  title =	{{Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{19:1--19:15},
  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.19},
  URN =		{urn:nbn:de:0030-drops-251516},
  doi =		{10.4230/LIPIcs.IPEC.2025.19},
  annote =	{Keywords: Parameterized complexity, connected odd cycle transversal, clique-width}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.15
Parameterized Complexity of Directed Traveling Salesman Problem

Authors: Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.
Cite as

Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý. Parameterized Complexity of Directed Traveling Salesman Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ISAAC.2025.15,
  author =	{Bla\v{z}ej, V\'{a}clav and Feldmann, Andreas Emil and Fioravantes, Foivos and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej},
  title =	{{Parameterized Complexity of Directed Traveling Salesman Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.15},
  URN =		{urn:nbn:de:0030-drops-249231},
  doi =		{10.4230/LIPIcs.ISAAC.2025.15},
  annote =	{Keywords: Directed TSP, parameterized complexity, vertex integrity, treedepth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.13
Tight Bounds for Some Classical Problems Parameterized by Cutwidth

Authors: Narek Bojikian, Vera Chekan, and Stefan Kratsch

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Cutwidth is a widely studied parameter and it quantifies how well a graph can be decomposed along small edge-cuts. It complements pathwidth, which captures decomposition by small vertex separators, and it is well-known that cutwidth upper-bounds pathwidth. The SETH-tight parameterized complexity of problems on graphs of bounded pathwidth (and treewidth) has been actively studied over the past decade while for cutwidth the complexity of many classical problems remained open. For Hamiltonian Cycle, it is known that a (2+√2)^{pw} n^𝒪(1) algorithm is optimal for pathwidth under SETH [Cygan et al. JACM 2018]. Van Geffen et al. [J. Graph Algorithms Appl. 2020] and Bojikian et al. [STACS 2023] asked which running time is optimal for this problem parameterized by cutwidth. We answer this question with (1+√2)^{ctw} n^𝒪(1) by providing matching upper and lower bounds. Second, as our main technical contribution, we close the gap left by van Heck [2018] for Partition Into Triangles (and Triangle Packing) by improving both upper and lower bound and getting a tight bound of ∛{3}^{ctw} n^𝒪(1), which to our knowledge exhibits the only known tight non-integral basis apart from Hamiltonian Cycle [Cygan et al. JACM 2018] and C₄-Hitting Set [SODA 2025]. We show that the cuts inducing a disjoint union of paths of length three (unions of so-called Z-cuts) lie at the core of the complexity of the problem - usually lower-bound constructions use simpler cuts inducing either a matching or a disjoint union of bicliques. Finally, we determine the optimal running times for Max Cut (2^{ctw} n^𝒪(1)) and Induced Matching (3^{ctw} n^𝒪(1)) by providing matching lower bounds for the existing algorithms - the latter result also answers an open question for treewidth by Chaudhary and Zehavi [WG 2023].
Cite as

Narek Bojikian, Vera Chekan, and Stefan Kratsch. Tight Bounds for Some Classical Problems Parameterized by Cutwidth. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.ESA.2025.13,
  author =	{Bojikian, Narek and Chekan, Vera and Kratsch, Stefan},
  title =	{{Tight Bounds for Some Classical Problems Parameterized by Cutwidth}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.13},
  URN =		{urn:nbn:de:0030-drops-244815},
  doi =		{10.4230/LIPIcs.ESA.2025.13},
  annote =	{Keywords: Parameterized complexity, cutwidth, Hamiltonian cycle, triangle packing, max cut, induced matching}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.17
Spectral Refutations of Semirandom k-LIN over Larger Fields

Authors: Nicholas Kocurek and Peter Manohar

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study the problem of strongly refuting semirandom k-LIN(𝔽) instances: systems of k-sparse inhomogeneous linear equations over a finite field 𝔽. For the case of 𝔽 = 𝔽₂, this is the well-studied problem of refuting semirandom instances of k-XOR, where the works of [Venkatesan Guruswami et al., 2022; Jun-Ting Hsieh et al., 2023] establish a tight trade-off between runtime and clause density for refutation: for any choice of a parameter 𝓁, they give an n^{O(𝓁)}-time algorithm to certify that there is no assignment that can satisfy more than 1/2 + ε-fraction of constraints in a semirandom k-XOR instance, provided that the instance has O(n)⋅(n/𝓁)^{k/2 - 1} log n/ε⁴ constraints, and the work of [Pravesh K. Kothari et al., 2017] provides good evidence that this tight up to a polylog(n) factor via lower bounds for the Sum-of-Squares hierarchy. However, for larger fields, the only known results for this problem are established via black-box reductions to the case of 𝔽₂, resulting in a |𝔽|^{3k} gap between the current best upper and lower bounds. In this paper, we give an algorithm for refuting semirandom k-LIN(𝔽) instances with the "correct" dependence on the field size |𝔽|. For any choice of a parameter 𝓁, our algorithm runs in (|𝔽|)^O(𝓁)-time and strongly refutes semirandom k-LIN(𝔽) instances with at least O(n) ⋅ (|𝔽^*| n/𝓁) ^{k/2 - 1} log(n|𝔽^*|)/ε⁴ constraints. We give good evidence that this dependence on the field size |𝔽| is optimal by proving a lower bound for the Sum-of-Squares hierarchy that matches this threshold up to a polylog(n |𝔽^*|) factor. Our results also extend beyond finite fields to the more general case of ℤ_m and arbitrary finite Abelian groups. Our key technical innovation is a generalization of the "𝔽₂ Kikuchi matrices" of [Alexander S. Wein et al., 2019; Venkatesan Guruswami et al., 2022] to larger fields, and finite Abelian groups more generally.
Cite as

Nicholas Kocurek and Peter Manohar. Spectral Refutations of Semirandom k-LIN over Larger Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kocurek_et_al:LIPIcs.APPROX/RANDOM.2025.17,
  author =	{Kocurek, Nicholas and Manohar, Peter},
  title =	{{Spectral Refutations of Semirandom k-LIN over Larger Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.17},
  URN =		{urn:nbn:de:0030-drops-243834},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.17},
  annote =	{Keywords: Spectral Algorithms, CSP Refutation, Kikuchi Matrices}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.39
Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems

Authors: Barış Can Esmer and Ariel Kulik

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this paper, we present Sampling with a Black Box, a unified framework for the design of parameterized approximation algorithms for vertex deletion problems (e.g., Vertex Cover, Feedback Vertex Set, etc.). The framework relies on two components: - A Sampling Step. A polynomial-time randomized algorithm that, given a graph G, returns a random vertex v such that the optimum of G⧵ {v} is smaller by 1 than the optimum of G, with some prescribed probability q. We show that such algorithms exist for multiple vertex deletion problems. - A Black Box algorithm which is either an exact parameterized algorithm, a polynomial-time approximation algorithm, or a parameterized-approximation algorithm. The framework combines these two components together. The sampling step is applied iteratively to remove vertices from the input graph, and then the solution is extended using the black box algorithm. The process is repeated sufficiently many times so that the target approximation ratio is attained with a constant probability. We use the technique to derive parameterized approximation algorithms for several vertex deletion problems, including Feedback Vertex Set, d-Hitting Set and 𝓁-Path Vertex Cover. In particular, for every approximation ratio 1 < β < 2, we attain a parameterized β-approximation for Feedback Vertex Set, which is faster than the parameterized β-approximation of [Jana, Lokshtanov, Mandal, Rai and Saurabh, MFCS 23']. Furthermore, our algorithms are always faster than the algorithms attained using Fidelity Preserving Transformations [Fellows, Kulik, Rosamond, and Shachnai, JCSS 18'].
Cite as

Barış Can Esmer and Ariel Kulik. Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canesmer_et_al:LIPIcs.ICALP.2025.39,
  author =	{Can Esmer, Bar{\i}\c{s} and Kulik, Ariel},
  title =	{{Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{39:1--39:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.39},
  URN =		{urn:nbn:de:0030-drops-234165},
  doi =		{10.4230/LIPIcs.ICALP.2025.39},
  annote =	{Keywords: Parameterized Approximation Algorithms, Random Sampling}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.4
Hardness and Approximation Algorithms for Balanced Districting Problems

Authors: Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
We introduce and study the problem of balanced districting, where given an undirected graph with vertices carrying two types of weights (different population, resource types, etc) the goal is to maximize the total weights covered in vertex disjoint districts such that each district is a star or (in general) a connected induced subgraph with the two weights to be balanced. This problem is strongly motivated by political redistricting, where contiguity, population balance, and compactness are essential. We provide hardness and approximation algorithms for this problem. In particular, we show NP-hardness for an approximation better than n^{1/2-δ} for any constant δ > 0 in general graphs even when the districts are star graphs, as well as NP-hardness on complete graphs, tree graphs, planar graphs and other restricted settings. On the other hand, we develop an algorithm for balanced star districting that gives an O(√n)-approximation on any graph (which is basically tight considering matching hardness of approximation results), an O(log n) approximation on planar graphs with extensions to minor-free graphs. Our algorithm uses a modified Whack-a-Mole algorithm [Bhattacharya, Kiss, and Saranurak, SODA 2023] to find a sparse solution of a fractional packing linear program (despite exponentially many variables) which requires a new design of a separation oracle specific for our balanced districting problem. To turn the fractional solution to a feasible integer solution, we adopt the randomized rounding algorithm by [Chan and Har-Peled, SoCG 2009]. To get a good approximation ratio of the rounding procedure, a crucial element in the analysis is the balanced scattering separators for planar graphs and minor-free graphs - separators that can be partitioned into a small number of k-hop independent sets for some constant k - which may find independent interest in solving other packing style problems. Further, our algorithm is versatile - the very same algorithm can be analyzed in different ways on various graph classes, which leads to class-dependent approximation ratios. We also provide a FPTAS algorithm for complete graphs and tree graphs, as well as greedy algorithms and approximation ratios when the district cardinality is bounded, the graph has bounded degree or the weights are binary. We refer the readers to the full version of the paper for complete set of results and proofs.
Cite as

Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu. Hardness and Approximation Algorithms for Balanced Districting Problems. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dharangutte_et_al:LIPIcs.FORC.2025.4,
  author =	{Dharangutte, Prathamesh and Gao, Jie and Huang, Shang-En and Yu, Fang-Yi},
  title =	{{Hardness and Approximation Algorithms for Balanced Districting Problems}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{4:1--4:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.4},
  URN =		{urn:nbn:de:0030-drops-231310},
  doi =		{10.4230/LIPIcs.FORC.2025.4},
  annote =	{Keywords: Approximation algorithms, algorithmic fairness}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.8
Enumeration of Minimal Hitting Sets Parameterized by Treewidth

Authors: Batya Kenig and Dan Shlomo Mizrahi

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
Enumerating the minimal hitting sets of a hypergraph is a problem which arises in many data management applications that include constraint mining, discovering unique column combinations, and enumerating database repairs. Previously, Eiter et al. [Thomas Eiter et al., 2003] showed that the minimal hitting sets of an n-vertex hypergraph, with treewidth w, can be enumerated with delay O^*(n^w) (ignoring polynomial factors), with space requirements that scale with the output size. We improve this to fixed-parameter-linear delay, following an FPT preprocessing phase. The memory consumption of our algorithm is exponential with respect to the treewidth of the hypergraph.
Cite as

Batya Kenig and Dan Shlomo Mizrahi. Enumeration of Minimal Hitting Sets Parameterized by Treewidth. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kenig_et_al:LIPIcs.ICDT.2025.8,
  author =	{Kenig, Batya and Mizrahi, Dan Shlomo},
  title =	{{Enumeration of Minimal Hitting Sets Parameterized by Treewidth}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.8},
  URN =		{urn:nbn:de:0030-drops-229498},
  doi =		{10.4230/LIPIcs.ICDT.2025.8},
  annote =	{Keywords: Enumeration, Hitting sets}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.36
MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal

Authors: Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity, Saket Saurabh, and Roohani Sharma

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In this paper, we study the parameterized complexity of the MaxMin versions of two fundamental separation problems: Maximum Minimal st-Separator and Maximum Minimal Odd Cycle Transversal (OCT), both parameterized by the solution size. In the Maximum Minimal st-Separator problem, given a graph G, two distinct vertices s and t and a positive integer k, the goal is to determine whether there exists a minimal st-separator in G of size at least k. Similarly, the Maximum Minimal OCT problem seeks to determine if there exists a minimal set of vertices whose deletion results in a bipartite graph, and whose size is at least k. We demonstrate that both problems are fixed-parameter tractable parameterized by k. Our FPT algorithm for Maximum Minimal st-Separator answers the open question by Hanaka, Bodlaender, van der Zanden & Ono [TCS 2019]. One unique insight from this work is the following. We use the meta-result of Lokshtanov, Ramanujan, Saurabh & Zehavi [ICALP 2018] that enables us to reduce our problems to highly unbreakable graphs. This is interesting, as an explicit use of the recursive understanding and randomized contractions framework of Chitnis, Cygan, Hajiaghayi, Pilipczuk & Pilipczuk [SICOMP 2016] to reduce to the highly unbreakable graphs setting (which is the result that Lokshtanov et al. tries to abstract out in their meta-theorem) does not seem obvious because certain "extension" variants of our problems are W[1]-hard.
Cite as

Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity, Saket Saurabh, and Roohani Sharma. MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gaikwad_et_al:LIPIcs.STACS.2025.36,
  author =	{Gaikwad, Ajinkya and Kumar, Hitendra and Maity, Soumen and Saurabh, Saket and Sharma, Roohani},
  title =	{{MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{36:1--36:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.36},
  URN =		{urn:nbn:de:0030-drops-228622},
  doi =		{10.4230/LIPIcs.STACS.2025.36},
  annote =	{Keywords: Parameterized Complexity, FPT, MaxMin problems, Maximum Minimal st-separator, Maximum Minimal Odd Cycle Transversal, Unbreakable Graphs, CMSO, Long Induced Odd Cycles, Sunflower Lemma}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.15
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems

Authors: Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can we simultaneously beat the running times of the fastest known (exponential-time) exact algorithms and the best known approximation factors that can be achieved in polynomial time? Following the recent research initiated by Esmer et al. (ESA 2022, IPEC 2023, SODA 2024) on vertex-subset problems, and by Inamdar et al. (ITCS 2024) on graph-partitioning problems, we focus on vertex-ordering problems. In particular, we give positive results for Feedback Arc Set, Optimal Linear Arrangement, Cutwidth, and Pathwidth. Most of our algorithms build upon a novel "balanced-cut" approach - which is our main conceptual contribution. This allows us to solve various problems in very general settings allowing for directed and arc-weighted input graphs. Our main technical contribution is a (1+ε)-approximation for any ε > 0 for (weighted) Feedback Arc Set in O^*((2-δ_ε)^n) time, where δ_ε > 0 is a constant only depending on ε.
Cite as

Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh. Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ITCS.2025.15,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Inamdar, Tanmay and Saurabh, Saket},
  title =	{{Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.15},
  URN =		{urn:nbn:de:0030-drops-226431},
  doi =		{10.4230/LIPIcs.ITCS.2025.15},
  annote =	{Keywords: Feedback Arc Set, Cutwidth, Optimal Linear Arrangement, Pathwidth}
}
Document
DOI: 10.4230/LIPIcs.WABI.2021.5
The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet

Authors: Nicolas Boria, Laurent Gourvès, Vangelis Th. Paschos, and Jérôme Monnot

Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)

Abstract
Given two strings A and B such that B is a permutation of A, the max duo-preservation string mapping (MPSM) problem asks to find a mapping π between them so as to preserve a maximum number of duos. A duo is any pair of consecutive characters in a string and it is preserved by π if its two consecutive characters in A are mapped to same two consecutive characters in B. This problem has received a growing attention in recent years, partly as an alternative way to produce approximation algorithms for its minimization counterpart, min common string partition, a widely studied problem due its applications in comparative genomics. Considering this favored field of application with short alphabet, it is surprising that MPSM^𝓁, the variant of MPSM with bounded alphabet, has received so little attention, with a single yet impressive work that provides a 2.67-approximation achieved in O(n) [Brubach, 2018], where n = |A| = |B|. Our work focuses on MPSM^𝓁, and our main contribution is the demonstration that this problem admits a Polynomial Time Approximation Scheme (PTAS) when 𝓁 = O(1). We also provide an alternate, somewhat simpler, proof of NP-hardness for this problem compared with the NP-hardness proof presented in [Haitao Jiang et al., 2012].
Cite as

Nicolas Boria, Laurent Gourvès, Vangelis Th. Paschos, and Jérôme Monnot. The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{boria_et_al:LIPIcs.WABI.2021.5,
  author =	{Boria, Nicolas and Gourv\`{e}s, Laurent and Paschos, Vangelis Th. and Monnot, J\'{e}r\^{o}me},
  title =	{{The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.5},
  URN =		{urn:nbn:de:0030-drops-143586},
  doi =		{10.4230/LIPIcs.WABI.2021.5},
  annote =	{Keywords: Maximum-Duo Preservation String Mapping, Bounded alphabet, Polynomial Time Approximation Scheme}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.9
New Algorithms for Mixed Dominating Set

Authors: Louis Dublois, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
A mixed dominating set is a set of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for MDS, resolving some open questions. In particular, we settle the problem’s complexity parameterized by treewidth and pathwidth by giving an algorithm running in time O^*(5^{tw}) (improving the current best O^*(6^{tw})), and a lower bound showing that our algorithm cannot be improved under the SETH, even if parameterized by pathwidth (improving a lower bound of O^*((2-ε)^{pw})). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve the best known FPT algorithm for this problem, from O^*(4.172^k) to O^*(3.510^k), and the best known exact algorithm, from O^*(2ⁿ) and exponential space, to O^*(1.912ⁿ) and polynomial space.
Cite as

Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. New Algorithms for Mixed Dominating Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dublois_et_al:LIPIcs.IPEC.2020.9,
  author =	{Dublois, Louis and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{New Algorithms for Mixed Dominating Set}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.9},
  URN =		{urn:nbn:de:0030-drops-133127},
  doi =		{10.4230/LIPIcs.IPEC.2020.9},
  annote =	{Keywords: FPT Algorithms, Exact Algorithms, Mixed Domination}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.7
Multistage Matchings

Authors: Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We consider a multistage version of the Perfect Matching problem which models the scenario where the costs of edges change over time and we seek to obtain a solution that achieves low total cost, while minimizing the number of changes from one instance to the next. Formally, we are given a sequence of edge-weighted graphs on the same set of vertices V, and are asked to produce a perfect matching in each instance so that the total edge cost plus the transition cost (the cost of exchanging edges), is minimized. This model was introduced by Gupta et al. (ICALP 2014), who posed as an open problem its approximability for bipartite instances. We completely resolve this question by showing that Minimum Multistage Perfect Matching (Min-MPM) does not admit an n^{1-epsilon}-approximation, even on bipartite instances with only two time steps. Motivated by this negative result, we go on to consider two variations of the problem. In Metric Minimum Multistage Perfect Matching problem (Metric-Min-MPM) we are promised that edge weights in each time step satisfy the triangle inequality. We show that this problem admits a 3-approximation when the number of time steps is 2 or 3. On the other hand, we show that even the metric case is APX-hard already for 2 time steps. We then consider the complementary maximization version of the problem, Maximum Multistage Perfect Matching problem (Max-MPM), where we seek to maximize the total profit of all selected edges plus the total number of non-exchanged edges. We show that Max-MPM is also APX-hard, but admits a constant factor approximation algorithm for any number of time steps.
Cite as

Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos. Multistage Matchings. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.SWAT.2018.7,
  author =	{Bampis, Evripidis and Escoffier, Bruno and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{Multistage Matchings}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.7},
  URN =		{urn:nbn:de:0030-drops-88338},
  doi =		{10.4230/LIPIcs.SWAT.2018.7},
  annote =	{Keywords: Perfect Matching, Temporal Optimization, Multistage Optimization}
}
  • Refine by Type
  • 19 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 11 2025
  • 1 2021
  • 1 2020
  • 2 2018
  • Show More...

  • Refine by Author
  • 6 Paschos, Vangelis Th.
  • 5 Lampis, Michael
  • 2 Bojikian, Narek
  • 2 Bonnet, Édouard
  • 2 Feldmann, Andreas Emil
  • Show More...

  • Refine by Series/Journal
  • 19 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Approximation algorithms analysis
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Fixed parameter tractability
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Enumeration
  • Show More...

  • Refine by Keyword
  • 2 Parameterized Algorithms
  • 2 Parameterized complexity
  • 2 treedepth
  • 1 Algorithm
  • 1 Approximation
  • 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