9 Search Results for "Král', Daniel"

Volume

LIPIcs, Volume 170

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

MFCS 2020, August 24-28, 2020, Prague, Czech Republic

Editors: Javier Esparza and Daniel Král'

Document
DOI: 10.4230/LIPIcs.MFCS.2024.66
Twin-Width of Graphs on Surfaces

Authors: Daniel Kráľ, Kristýna Pekárková, and Kenny Štorgel

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Twin-width is a width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. Hliněný and Jedelský [ICALP'23] showed that every planar graph has twin-width at most 8. We prove that the twin-width of every graph embeddable in a surface of Euler genus g is at most 18√{47g} + O(1), which is asymptotically best possible as it asymptotically differs from the lower bound by a constant multiplicative factor. Our proof also yields a quadratic time algorithm to find a corresponding contraction sequence. To prove the upper bound on twin-width of graphs embeddable in surfaces, we provide a stronger version of the Product Structure Theorem for graphs of Euler genus g that asserts that every such graph is a subgraph of the strong product of a path and a graph with a tree-decomposition with all bags of size at most eight with a single exceptional bag of size max{6, 32g-37}.
Cite as

Daniel Kráľ, Kristýna Pekárková, and Kenny Štorgel. Twin-Width of Graphs on Surfaces. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kral_et_al:LIPIcs.MFCS.2024.66,
  author =	{Kr\'{a}\v{l}, Daniel and Pek\'{a}rkov\'{a}, Krist\'{y}na and \v{S}torgel, Kenny},
  title =	{{Twin-Width of Graphs on Surfaces}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{66:1--66:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.66},
  URN =		{urn:nbn:de:0030-drops-206226},
  doi =		{10.4230/LIPIcs.MFCS.2024.66},
  annote =	{Keywords: twin-width, graphs on surfaces, fixed parameter tractability}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.29
Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming

Authors: Marcin Briański, Martin Koutecký, Daniel Král', Kristýna Pekárková, and Felix Schröder

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to an equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the 𝓁₁-norm of the Graver basis is bounded by a function of the maximum 𝓁₁-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such an equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the 𝓁₁-norm of the Graver basis of the constraint matrix, when parameterized by the 𝓁₁-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix equivalent to the constraint matrix.
Cite as

Marcin Briański, Martin Koutecký, Daniel Král', Kristýna Pekárková, and Felix Schröder. Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{brianski_et_al:LIPIcs.ICALP.2022.29,
  author =	{Bria\'{n}ski, Marcin and Kouteck\'{y}, Martin and Kr\'{a}l', Daniel and Pek\'{a}rkov\'{a}, Krist\'{y}na and Schr\"{o}der, Felix},
  title =	{{Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{29:1--29:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.29},
  URN =		{urn:nbn:de:0030-drops-163702},
  doi =		{10.4230/LIPIcs.ICALP.2022.29},
  annote =	{Keywords: Integer programming, width parameters, matroids, Graver basis, tree-depth, fixed parameter tractability}
}
Document
DOI: 10.4230/DagRep.11.8.115
Sparsity in Algorithms, Combinatorics and Logic (Dagstuhl Seminar 21391)

Authors: Daniel Král’, Michał Pilipczuk, Sebastian Siebertz, and Blair D. Sullivan

Published in: Dagstuhl Reports, Volume 11, Issue 8 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21391 "Sparsity in Algorithms, Combinatorics and Logic". The seminar took place in a hybrid format from September 26 - October 1, 2021 and brought together 61 researchers. This report includes a discussion of the motivation of the seminar, presentation of the overall organization, abstracts of talks, and a report from each of the working groups.
Cite as

Daniel Král’, Michał Pilipczuk, Sebastian Siebertz, and Blair D. Sullivan. Sparsity in Algorithms, Combinatorics and Logic (Dagstuhl Seminar 21391). In Dagstuhl Reports, Volume 11, Issue 8, pp. 115-128, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{kral'_et_al:DagRep.11.8.115,
  author =	{Kr\'{a}l’, Daniel and Pilipczuk, Micha{\l} and Siebertz, Sebastian and Sullivan, Blair D.},
  title =	{{Sparsity in Algorithms, Combinatorics and Logic (Dagstuhl Seminar 21391)}},
  pages =	{115--128},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{8},
  editor =	{Kr\'{a}l’, Daniel and Pilipczuk, Micha{\l} and Siebertz, Sebastian and Sullivan, Blair D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.8.115},
  URN =		{urn:nbn:de:0030-drops-157718},
  doi =		{10.4230/DagRep.11.8.115},
  annote =	{Keywords: Algorithm design, Parameterised complexity, Sparse graphs, Graph decompositions, Model theory}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.MFCS.2020
LIPIcs, Volume 170, MFCS 2020, Complete Volume

Authors: Javier Esparza and Daniel Král'

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
LIPIcs, Volume 170, MFCS 2020, Complete Volume
Cite as

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 1-1216, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{esparza_et_al:LIPIcs.MFCS.2020,
  title =	{{LIPIcs, Volume 170, MFCS 2020, Complete Volume}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{1--1216},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020},
  URN =		{urn:nbn:de:0030-drops-126703},
  doi =		{10.4230/LIPIcs.MFCS.2020},
  annote =	{Keywords: LIPIcs, Volume 170, MFCS 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.MFCS.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Javier Esparza and Daniel Král'

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{esparza_et_al:LIPIcs.MFCS.2020.0,
  author =	{Esparza, Javier and Kr\'{a}l', Daniel},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.0},
  URN =		{urn:nbn:de:0030-drops-126714},
  doi =		{10.4230/LIPIcs.MFCS.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.26
Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming

Authors: Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král', and Kristýna Pekárková

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with tree-depth d and largest entry Δ are solvable in time g(d,Δ) poly(n) for some function g, i.e., fixed parameter tractable when parameterized by tree-depth d and Δ. However, the tree-depth of a constraint matrix depends on the positions of its non-zero entries and thus does not reflect its geometric structure. In particular, tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth. We prove that the branch-depth of the matroid defined by the columns of the constraint matrix is equal to the minimum tree-depth of a row-equivalent matrix. We also design a fixed parameter algorithm parameterized by an integer d and the entry complexity of an input matrix that either outputs a matrix with the smallest dual tree-depth that is row-equivalent to the input matrix or outputs that there is no matrix with dual tree-depth at most d that is row-equivalent to the input matrix. Finally, we use these results to obtain a fixed parameter algorithm for integer programming parameterized by the branch-depth of the input constraint matrix and the entry complexity. The parameterization by branch-depth cannot be replaced by the more permissive notion of branch-width.
Cite as

Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král', and Kristýna Pekárková. Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ICALP.2020.26,
  author =	{Chan, Timothy F. N. and Cooper, Jacob W. and Kouteck\'{y}, Martin and Kr\'{a}l', Daniel and Pek\'{a}rkov\'{a}, Krist\'{y}na},
  title =	{{Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.26},
  URN =		{urn:nbn:de:0030-drops-124339},
  doi =		{10.4230/LIPIcs.ICALP.2020.26},
  annote =	{Keywords: Matroid algorithms, width parameters, integer programming, fixed parameter tractability, branch-width, branch-depth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.29
Recovering Sparse Graphs

Authors: Jakub Gajarský and Daniel Král'

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices. Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes of sparse graphs. We derive as a corollary that if G is a graph class with bounded expansion, then the first order model checking is fixed parameter tractable in the class of all graphs that can obtained from a graph G in G by complementing on at most k arbitrary subsets of the vertex set of G; this implies an earlier result that the first order model checking is fixed parameter tractable in graph classes interpretable in classes of graphs with bounded maximum degree.
Cite as

Jakub Gajarský and Daniel Král'. Recovering Sparse Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.MFCS.2018.29,
  author =	{Gajarsk\'{y}, Jakub and Kr\'{a}l', Daniel},
  title =	{{Recovering Sparse Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.29},
  URN =		{urn:nbn:de:0030-drops-96111},
  doi =		{10.4230/LIPIcs.MFCS.2018.29},
  annote =	{Keywords: model checking, degenerate graphs, interpretations, bounded expansion}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.27
Graphic TSP in Cubic Graphs

Authors: Zdenek Dvorák, Daniel Král, and Bojan Mohar

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.
Cite as

Zdenek Dvorák, Daniel Král, and Bojan Mohar. Graphic TSP in Cubic Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.STACS.2017.27,
  author =	{Dvor\'{a}k, Zdenek and Kr\'{a}l, Daniel and Mohar, Bojan},
  title =	{{Graphic TSP in Cubic Graphs}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.27},
  URN =		{urn:nbn:de:0030-drops-70068},
  doi =		{10.4230/LIPIcs.STACS.2017.27},
  annote =	{Keywords: Graphic TSP, approximation algorithms, cubic graphs}
}
  • Refine by Author
  • 5 Král', Daniel
  • 3 Pekárková, Kristýna
  • 2 Esparza, Javier
  • 2 Koutecký, Martin
  • 1 Briański, Marcin
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 fixed parameter tractability
  • 2 width parameters
  • 1 Algorithm design
  • 1 Conference Organization
  • 1 Front Matter
  • Show More...

  • Refine by Type
  • 8 document
  • 1 volume

  • Refine by Publication Year
  • 4 2020
  • 2 2022
  • 1 2017
  • 1 2018
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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