Search Results

Documents authored by Balabán, Jakub

Document
DOI: 10.4230/LIPIcs.MFCS.2025.12
Online Knapsack Problems with Estimates

Authors: Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to. When you are aware of all possible events and their costs at the beginning of the year, you can select the subset of the possible events that maximizes your happiness and is within your budget. On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future. These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic: Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices. We model this problem within the setting of online knapsack problems with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy δ (i.e., when each actual item size can deviate by ± δ from the announced size) for both the simple knapsack (also known as subset sum problem) and the simple knapsack with removability.
Cite as

Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker. Online Knapsack Problems with Estimates. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.12,
  author =	{Balab\'{a}n, Jakub and Gehnen, Matthias and Lotze, Henri and Seesemann, Finn and Stocker, Moritz},
  title =	{{Online Knapsack Problems with Estimates}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.12},
  URN =		{urn:nbn:de:0030-drops-241190},
  doi =		{10.4230/LIPIcs.MFCS.2025.12},
  annote =	{Keywords: Knapsack, Online Knapsack, Removability, Estimate, Prediction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.13
Solving Partial Dominating Set and Related Problems Using Twin-Width

Authors: Jakub Balabán, Daniel Mock, and Peter Rossmanith

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are W[1]-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form ϕ≡∃ x₁⋯ ∃ x_k ∑_{α ∈ I} #y ψ_α(x₁,…,x_k,y) ≥ t, where ψ_α is a quantifier-free formula for each α ∈ I, t is an arbitrary number, and #y is a counting quantifier, can be evaluated in time f(d,k)n, where n is the number of vertices and d is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.
Cite as

Jakub Balabán, Daniel Mock, and Peter Rossmanith. Solving Partial Dominating Set and Related Problems Using Twin-Width. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.13,
  author =	{Balab\'{a}n, Jakub and Mock, Daniel and Rossmanith, Peter},
  title =	{{Solving Partial Dominating Set and Related Problems Using Twin-Width}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.13},
  URN =		{urn:nbn:de:0030-drops-241203},
  doi =		{10.4230/LIPIcs.MFCS.2025.13},
  annote =	{Keywords: Partial Dominating Set, Partial Vertex Cover, meta-algorithm, counting logic, twin-width}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.3
Twin-Width Meets Feedback Edges and Vertex Integrity

Authors: Jakub Balabán, Robert Ganian, and Mathis Rocton

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number. Here, we make several new steps in this research direction and obtain: - An asymptotically tight bound between twin-width and the feedback edge number; - A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency; - An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph.
Cite as

Jakub Balabán, Robert Ganian, and Mathis Rocton. Twin-Width Meets Feedback Edges and Vertex Integrity. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.IPEC.2024.3,
  author =	{Balab\'{a}n, Jakub and Ganian, Robert and Rocton, Mathis},
  title =	{{Twin-Width Meets Feedback Edges and Vertex Integrity}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.3},
  URN =		{urn:nbn:de:0030-drops-222293},
  doi =		{10.4230/LIPIcs.IPEC.2024.3},
  annote =	{Keywords: twin-width, fixed-parameter algorithms, feedback edge number, vertex integrity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.7
Computing Twin-Width Parameterized by the Feedback Edge Number

Authors: Jakub Balabán, Robert Ganian, and Mathis Rocton

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The problem of whether and how one can compute the twin-width of a graph - along with an accompanying contraction sequence - lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an 𝓁-contraction sequence (for an arbitrary specified 𝓁) or determines that the twin-width of the input graph is at least 𝓁. These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number.
Cite as

Jakub Balabán, Robert Ganian, and Mathis Rocton. Computing Twin-Width Parameterized by the Feedback Edge Number. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.STACS.2024.7,
  author =	{Balab\'{a}n, Jakub and Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width Parameterized by the Feedback Edge Number}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.7},
  URN =		{urn:nbn:de:0030-drops-197170},
  doi =		{10.4230/LIPIcs.STACS.2024.7},
  annote =	{Keywords: twin-width, parameterized complexity, kernelization, feedback edge number}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.6
Twin-Width Is Linear in the Poset Width

Authors: Jakub Balabán and Petr Hliněný

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced just very recently, in 2020 by Bonnet, Kim, Thomassé and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result, they also claimed that posets of bounded width have bounded twin-width, thus capturing prior result on FO model checking of posets of bounded width in FPT. However, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. We prove that posets of width d have twin-width at most 8d with a direct and elementary argument, and show that this bound is tight up to a constant factor. Specifically, for posets of width 2 we prove that in the worst case their twin-width is also equal 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset.
Cite as

Jakub Balabán and Petr Hliněný. Twin-Width Is Linear in the Poset Width. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.IPEC.2021.6,
  author =	{Balab\'{a}n, Jakub and Hlin\v{e}n\'{y}, Petr},
  title =	{{Twin-Width Is Linear in the Poset Width}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.6},
  URN =		{urn:nbn:de:0030-drops-153895},
  doi =		{10.4230/LIPIcs.IPEC.2021.6},
  annote =	{Keywords: twin-width, digraph, poset, FO model checking, contraction sequence}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact