111 Search Results for "Peleg, David"

Volume

LIPIcs, Volume 272

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

MFCS 2023, August 28 to September 1, 2023, Bordeaux, France

Editors: Jérôme Leroux, Sylvain Lombardy, and David Peleg

Document
Complete Volume
DOI: 10.4230/LIPIcs.MFCS.2023
LIPIcs, Volume 272, MFCS 2023, Complete Volume

Authors: Jérôme Leroux, Sylvain Lombardy, and David Peleg

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
LIPIcs, Volume 272, MFCS 2023, Complete Volume
Cite as

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 1-1302, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{leroux_et_al:LIPIcs.MFCS.2023,
  title =	{{LIPIcs, Volume 272, MFCS 2023, Complete Volume}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{1--1302},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023},
  URN =		{urn:nbn:de:0030-drops-185332},
  doi =		{10.4230/LIPIcs.MFCS.2023},
  annote =	{Keywords: LIPIcs, Volume 272, MFCS 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.MFCS.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Jérôme Leroux, Sylvain Lombardy, and David Peleg

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

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

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

Copy BibTex To Clipboard

@InProceedings{leroux_et_al:LIPIcs.MFCS.2023.0,
  author =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.0},
  URN =		{urn:nbn:de:0030-drops-185349},
  doi =		{10.4230/LIPIcs.MFCS.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.1
Exploring the Space of Colourings with Kempe Changes (Invited Talk)

Authors: Marthe Bonamy

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Kempe changes were introduced in 1879 in an attempt to prove the 4-colour theorem. They are a convenient if not crucial tool to prove various colouring theorems. Here, we consider how to navigate from a colouring to another through Kempe changes. When is it possible? How fast?
Cite as

Marthe Bonamy. Exploring the Space of Colourings with Kempe Changes (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 1:1-1:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bonamy:LIPIcs.MFCS.2023.1,
  author =	{Bonamy, Marthe},
  title =	{{Exploring the Space of Colourings with Kempe Changes}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{1:1--1:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.1},
  URN =		{urn:nbn:de:0030-drops-185350},
  doi =		{10.4230/LIPIcs.MFCS.2023.1},
  annote =	{Keywords: Graph theory, graph coloring, reconfiguration}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.2
Online Algorithms with Predictions (Invited Talk)

Authors: Joan Boyar

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We give an introduction to online algorithms with predictions, from an algorithms researcher’s perspective, concentrating on minimization problems.
Cite as

Joan Boyar. Online Algorithms with Predictions (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boyar:LIPIcs.MFCS.2023.2,
  author =	{Boyar, Joan},
  title =	{{Online Algorithms with Predictions}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.2},
  URN =		{urn:nbn:de:0030-drops-185368},
  doi =		{10.4230/LIPIcs.MFCS.2023.2},
  annote =	{Keywords: Online algorithms with predictions, online algorithms with advice, random order analysis}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.3
Modern Parallel Algorithms (Invited Talk)

Authors: Artur Czumaj

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Recent advances in the design of efficient parallel algorithms have been largely focusing on the nowadays classical model of parallel computing called Massive Parallel Computation (MPC), which follows the framework of MapReduce systems. In this talk we will survey recent advances in the design of algorithms for graph problems for the MPC model and will mention some interesting open questions in this area.
Cite as

Artur Czumaj. Modern Parallel Algorithms (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 3:1-3:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{czumaj:LIPIcs.MFCS.2023.3,
  author =	{Czumaj, Artur},
  title =	{{Modern Parallel Algorithms}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{3:1--3:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.3},
  URN =		{urn:nbn:de:0030-drops-185378},
  doi =		{10.4230/LIPIcs.MFCS.2023.3},
  annote =	{Keywords: Distributed computing, parallel computing}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.4
Algebraic Reasoning for (Un)Solvable Loops (Invited Talk)

Authors: Laura Kovács

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Loop invariants describe valid program properties that hold before and after every loop iteration. As such, loop invariants are the workhorses in formalizing loop semantics and automating the formal analysis and verification of programs with loops. While automatically synthesizing loop invariants is, in general, an uncomputable problem, when considering only single-path loops with linear updates (linear loops), the strongest polynomial invariant is in fact computable [Michael Karr, 1976; Markus Müller-Olm and Helmut Seidl, 2004; Laura Kovács, 2008; Ehud Hrushovski et al., 2018]. Yet, already for loops with "only" polynomial updates, computing the strongest invariant has been an open challenge since 2004 [Markus Müller-Olm and Helmut Seidl, 2004]. In this invited talk, we first present computability results on polynomial invariant synthesis for restricted polynomial loops, called solvable loops [Rodríguez-Carbonell and Kapur, 2004]. Key to solvable loops is that one can automatically compute invariants from closed-form solutions of algebraic recurrence equations that model the loop behaviour [Laura Kovács, 2008; Andreas Humenberger et al., 2017]. We also establish a technique for invariant synthesis for classes of loops that are not solvable, termed unsolvable loops [Daneshvar Amrollahi et al., 2022]. We next study the limits of computability in deriving the (strongest) polynomial invariants for arbitrary polynomial loops. We prove that computing the strongest polynomial invariant of arbitrary, single-path polynomial loops is very hard [Julian Müllner, 2023] - namely, it is at least as hard as the Skolem problem [Graham Everest et al., 2003; Terrence Tao, 2008], a prominent algebraic problem in the theory of linear recurrences. Going beyond single-path loops, we show that the strongest polynomial invariant is uncomputable already for multi-path polynomial loops with arbitrary quadratic polynomial updates [Laura Kovács and Anton Varonka, 2023].
Cite as

Laura Kovács. Algebraic Reasoning for (Un)Solvable Loops (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 4:1-4:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kovacs:LIPIcs.MFCS.2023.4,
  author =	{Kov\'{a}cs, Laura},
  title =	{{Algebraic Reasoning for (Un)Solvable Loops}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{4:1--4:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.4},
  URN =		{urn:nbn:de:0030-drops-185385},
  doi =		{10.4230/LIPIcs.MFCS.2023.4},
  annote =	{Keywords: Symbolic Computation, Formal Methods, Loop Analysis, Polynomial Invariants}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.5
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk)

Authors: Nina Klobas, George B. Mertzios, and Paul G. Spirakis

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Graphs are fundamental tools for modelling relations among objects in various scientific fields. However, traditional static graphs have limitations when it comes to capturing the dynamic nature of real-world systems. To overcome this limitation, temporal graphs have been introduced as a framework to model graphs that change over time. In temporal graphs the edges among vertices appear and disappear at specific time steps, reflecting the temporal dynamics of the observed system, which allows us to analyse time dependent patterns and processes. In this paper we focus on the research related to sliding time windows in temporal graphs. Sliding time windows offer a way to analyse specific time intervals within the lifespan of a temporal graph. By sliding the window along the timeline, we can examine the graph’s characteristics and properties within different time periods. This paper provides an overview of the research on sliding time windows in temporal graphs. Although progress has been made in this field, there are still many interesting questions and challenges to be explored. We discuss some of the open problems and highlight their potential for future research.
Cite as

Nina Klobas, George B. Mertzios, and Paul G. Spirakis. Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 5:1-5:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{klobas_et_al:LIPIcs.MFCS.2023.5,
  author =	{Klobas, Nina and Mertzios, George B. and Spirakis, Paul G.},
  title =	{{Sliding into the Future: Investigating Sliding Windows in Temporal Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.5},
  URN =		{urn:nbn:de:0030-drops-185397},
  doi =		{10.4230/LIPIcs.MFCS.2023.5},
  annote =	{Keywords: Temporal Graphs, Sliding Time Windows}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.6
Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes

Authors: Faisal N. Abu-Khzam, Henning Fernau, and Kevin Mann

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The concept of Roman domination has recently been studied concerning enumerating and counting in F. N. Abu-Khzam et al. (WG 2022). More technically speaking, a function that assigns 0,1,2 to the vertices of an undirected graph is called a Roman dominating function if each vertex assigned zero has a neighbor assigned two. Such a function is called minimal if decreasing any assignment to any vertex would yield a function that is no longer a Roman dominating function. It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, i.e., between any two outputs of a solution, no more than polynomial time will elapse. This contrasts what is known about minimal dominating sets, where the question whether or not these can be enumerated with polynomial delay is open for more than 40 years. This makes the concept of Roman domination rather special and interesting among the many variants of domination problems studied in the literature, as it has been shown for several of these variants that the question of enumerating minimal solutions is tightly linked to that of enumerating minimal dominating sets, see M. Kanté et al. in SIAM J. Disc. Math., 2014. The running time of the mentioned enumeration algorithm for minimal Roman dominating functions (Abu-Khzam et al., WG 2022) could be estimated as 𝒪(1.9332ⁿ) on general graphs of order n. Here, we focus on special graph classes, as has been also done for enumerating minimal dominating sets before. More specifically, for chordal graphs, we present an enumeration algorithm running in time 𝒪(1.8940ⁿ). It is unknown if this gives a tight bound on the maximum number of minimal Roman dominating functions in chordal graphs. For interval graphs, we can lower this time bound further to 𝒪(1.7321ⁿ), which also matches the known lower bound concerning the maximum number of minimal Roman dominating functions. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely 𝒪^*(√3ⁿ). Furthermore, we present an optimal enumeration algorithm running in time 𝒪^*(∛3ⁿ) for split graphs and for cobipartite graphs, i.e., we can also give a matching lower bound example for these graph classes. Hence, our enumeration algorithms for interval graphs, forests, split graphs and cobipartite graphs are all optimal. The importance of our results stems from the fact that, for other types of domination problems, optimal enumeration algorithms are not always found. Interestingly, we use a different form of analysis for the running times of our different algorithms, and the branchings had to be tailored and tweaked to obtain the intended optimality results. Our Roman dominating functions enumeration algorithm for trees and forests is distinctively different from the one for minimal dominating sets by Rote (SODA 2019).Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on more concrete graph families like paths.
Cite as

Faisal N. Abu-Khzam, Henning Fernau, and Kevin Mann. Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 6:1-6:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abukhzam_et_al:LIPIcs.MFCS.2023.6,
  author =	{Abu-Khzam, Faisal N. and Fernau, Henning and Mann, Kevin},
  title =	{{Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.6},
  URN =		{urn:nbn:de:0030-drops-185400},
  doi =		{10.4230/LIPIcs.MFCS.2023.6},
  annote =	{Keywords: special graph classes, counting problems, enumeration problems, domination problems, Roman domination}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.7
Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes

Authors: Antonis Achilleos and Aggeliki Chalki

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We present quantitative logics with two-step semantics based on the framework of quantitative logics introduced by Arenas et al. (2020) and the two-step semantics defined in the context of weighted logics by Gastin & Monmege (2018). We show that some of the fragments of our logics augmented with a least fixed point operator capture interesting classes of counting problems. Specifically, we answer an open question in the area of descriptive complexity of counting problems by providing logical characterisations of two subclasses of #P, namely SpanL and TotP, that play a significant role in the study of approximable counting problems. Moreover, we define logics that capture FPSPACE and SpanPSPACE, which are counting versions of PSPACE.
Cite as

Antonis Achilleos and Aggeliki Chalki. Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 7:1-7:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{achilleos_et_al:LIPIcs.MFCS.2023.7,
  author =	{Achilleos, Antonis and Chalki, Aggeliki},
  title =	{{Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.7},
  URN =		{urn:nbn:de:0030-drops-185412},
  doi =		{10.4230/LIPIcs.MFCS.2023.7},
  annote =	{Keywords: descriptive complexity, quantitative logics, counting problems, #P}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.8
Recognizing H-Graphs - Beyond Circular-Arc Graphs

Authors: Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz, Tim A. Hartmann, Petr Hliněný, Jan Kratochvíl, Tomasz Krawczyk, and Peter Zeman

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph H, the class of H-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of H. Such classes of graphs are related to many known graph classes: for example, K₂-graphs coincide with interval graphs, K₃-graphs with circular-arc graphs, the union of T-graphs, where T ranges over all trees, coincides with chordal graphs. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of H-graphs for different graphs H. In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Töpfer, Voborník, and Zeman showed an XP-algorithm testing whether a given graph is a T-graph, where the parameter is the size of the tree T. In particular, for every fixed tree T the recognition of T-graphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing K₃-graphs (circular-arc graphs). On the other hand, Chaplick et al. showed also that for every fixed graph H containing two distinct cycles sharing an edge, the recognition of H-graphs is NP-hard. The main two results of this work narrow the gap between the NP-hard and 𝖯 cases of H-graph recognition. First, we show that the recognition of H-graphs is NP-hard when H contains two distinct cycles. On the other hand, we show a polynomial-time algorithm recognizing L-graphs, where L is a graph containing a cycle and an edge attached to it (which we call lollipop graphs). Our work leaves open the recognition problems of M-graphs for every unicyclic graph M different from a cycle and a lollipop.
Cite as

Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz, Tim A. Hartmann, Petr Hliněný, Jan Kratochvíl, Tomasz Krawczyk, and Peter Zeman. Recognizing H-Graphs - Beyond Circular-Arc Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 8:1-8:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agaoglucagirici_et_al:LIPIcs.MFCS.2023.8,
  author =	{A\u{g}ao\u{g}lu \c{C}a\u{g}{\i}r{\i}c{\i}, Deniz and \c{C}a\u{g}{\i}r{\i}c{\i}, Onur and Derbisz, Jan and Hartmann, Tim A. and Hlin\v{e}n\'{y}, Petr and Kratochv{\'\i}l, Jan and Krawczyk, Tomasz and Zeman, Peter},
  title =	{{Recognizing H-Graphs - Beyond Circular-Arc Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.8},
  URN =		{urn:nbn:de:0030-drops-185420},
  doi =		{10.4230/LIPIcs.MFCS.2023.8},
  annote =	{Keywords: H-graphs, Intersection Graphs, Helly Property}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.9
Descriptive Complexity for Distributed Computing with Circuits

Authors: Veeti Ahvonen, Damian Heiman, Lauri Hella, and Antti Kuusisto

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We consider distributed algorithms in the realistic scenario where distributed message passing is operated by circuits. We show that within this setting, modal substitution calculus MSC precisely captures the expressive power of circuits. The result is established via constructing translations that are highly efficient in relation to size. We also observe that the coloring algorithm based on Cole-Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.
Cite as

Veeti Ahvonen, Damian Heiman, Lauri Hella, and Antti Kuusisto. Descriptive Complexity for Distributed Computing with Circuits. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 9:1-9:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ahvonen_et_al:LIPIcs.MFCS.2023.9,
  author =	{Ahvonen, Veeti and Heiman, Damian and Hella, Lauri and Kuusisto, Antti},
  title =	{{Descriptive Complexity for Distributed Computing with Circuits}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.9},
  URN =		{urn:nbn:de:0030-drops-185433},
  doi =		{10.4230/LIPIcs.MFCS.2023.9},
  annote =	{Keywords: Descriptive complexity, distributed computing, logic, graph coloring}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.10
Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii-Mann Iteration

Authors: Marianne Akian, Stéphane Gaubert, Ulysse Naepels, and Basile Terver

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We analyse an algorithm solving stochastic mean-payoff games, combining the ideas of relative value iteration and of Krasnoselskii-Mann damping. We derive parameterized complexity bounds for several classes of games satisfying irreducibility conditions. We show in particular that an ε-approximation of the value of an irreducible concurrent stochastic game can be computed in a number of iterations in O(|log(ε)|) where the constant in the O(⋅) is explicit, depending on the smallest non-zero transition probabilities. This should be compared with a bound in O(ε^{-1}|log(ε)|) obtained by Chatterjee and Ibsen-Jensen (ICALP 2014) for the same class of games, and to a O(ε^{-1}) bound by Allamigeon, Gaubert, Katz and Skomra (ICALP 2022) for turn-based games. We also establish parameterized complexity bounds for entropy games, a class of matrix multiplication games introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. We derive these results by methods of variational analysis, establishing contraction properties of the relative Krasnoselskii-Mann iteration with respect to Hilbert’s semi-norm.
Cite as

Marianne Akian, Stéphane Gaubert, Ulysse Naepels, and Basile Terver. Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii-Mann Iteration. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 10:1-10:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{akian_et_al:LIPIcs.MFCS.2023.10,
  author =	{Akian, Marianne and Gaubert, St\'{e}phane and Naepels, Ulysse and Terver, Basile},
  title =	{{Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii-Mann Iteration}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.10},
  URN =		{urn:nbn:de:0030-drops-185448},
  doi =		{10.4230/LIPIcs.MFCS.2023.10},
  annote =	{Keywords: Stochastic mean-payoff games, concurrent games, entropy games, relative value iteration, Krasnoselskii-Mann fixed point algorithm, Hilbert projective metric}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.11
The Geometry of Reachability in Continuous Vector Addition Systems with States

Authors: Shaull Almagor, Arka Ghosh, Tim Leys, and Guillermo A. Pérez

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study the geometry of reachability sets of continuous vector addition systems with states (VASS). In particular we establish that they are "almost" Minkowski sums of convex cones and zonotopes generated by the vectors labelling the transitions of the VASS. We use the latter to prove that short so-called linear path schemes suffice as witnesses of reachability in continuous VASS. Then, we give new polynomial-time algorithms for the reachability problem for linear path schemes. Finally, we also establish that enriching the model with zero tests makes the reachability problem intractable already for linear path schemes of dimension two.
Cite as

Shaull Almagor, Arka Ghosh, Tim Leys, and Guillermo A. Pérez. The Geometry of Reachability in Continuous Vector Addition Systems with States. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 11:1-11:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{almagor_et_al:LIPIcs.MFCS.2023.11,
  author =	{Almagor, Shaull and Ghosh, Arka and Leys, Tim and P\'{e}rez, Guillermo A.},
  title =	{{The Geometry of Reachability in Continuous Vector Addition Systems with States}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.11},
  URN =		{urn:nbn:de:0030-drops-185457},
  doi =		{10.4230/LIPIcs.MFCS.2023.11},
  annote =	{Keywords: Vector addition system with states, reachability, continuous approximation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.12
Competitive Search in the Line and the Star with Predictions

Authors: Spyros Angelopoulos

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study the classic problem of searching for a hidden target in the line and the m-ray star, in a setting in which the searcher has some prediction on the hider’s position. We first focus on the main metric for comparing search strategies under predictions; namely, we give positive and negative results on the consistency-robustness tradeoff, where the performance of the strategy is evaluated at extreme situations in which the prediction is either error-free, or adversarially generated, respectively. For the line, we show tight bounds concerning this tradeoff, under the untrusted advice model, in which the prediction is in the form of a k-bit string which encodes the responses to k binary queries. For the star, we give tight, and near-tight tradeoffs in the positional and the directional models, in which the prediction is related to the position of the target within the star, and to the ray on which the target hides, respectively. Last, for all three prediction models, we show how to generalize our study to a setting in which the performance of the strategy is evaluated as a function of the searcher’s desired tolerance to prediction errors, both in terms of positive and inapproximability results.
Cite as

Spyros Angelopoulos. Competitive Search in the Line and the Star with Predictions. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{angelopoulos:LIPIcs.MFCS.2023.12,
  author =	{Angelopoulos, Spyros},
  title =	{{Competitive Search in the Line and the Star with Predictions}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.12},
  URN =		{urn:nbn:de:0030-drops-185464},
  doi =		{10.4230/LIPIcs.MFCS.2023.12},
  annote =	{Keywords: Search problems, line and star search, competitive ratio, predictions, consistency and robustness}
}
  • Refine by Author
  • 17 Peleg, David
  • 8 Bar-Noy, Amotz
  • 8 Rawitz, Dror
  • 4 Choudhary, Keerti
  • 3 Böhnlein, Toni
  • Show More...

  • Refine by Classification
  • 10 Mathematics of computing → Graph algorithms
  • 8 Mathematics of computing → Graph theory
  • 8 Theory of computation → Distributed algorithms
  • 8 Theory of computation → Parameterized complexity and exact algorithms
  • 7 Theory of computation → Logic and verification
  • Show More...

  • Refine by Keyword
  • 3 Bipartite Graphs
  • 3 Graph Realization
  • 3 Graph realization
  • 2 Asynchronous networks
  • 2 Bigraphic Sequences
  • Show More...

  • Refine by Type
  • 110 document
  • 1 volume

  • Refine by Publication Year
  • 92 2023
  • 6 2022
  • 5 2021
  • 3 2020
  • 2 2010
  • Show More...

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact