Volume
LIPIcs, Volume 241
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS)
Event
MFCS 2022, August 22-26, 2022, Vienna, AustriaEditors
Publication Details
- published at: 2022-08-22
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-256-3
- DBLP: db/conf/mfcs/mfcs2022
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 241, MFCS 2022, Complete Volume
Abstract
LIPIcs, Volume 241, MFCS 2022, Complete Volume
Cite as
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 1-1236, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@Proceedings{szeider_et_al:LIPIcs.MFCS.2022,
title = {{LIPIcs, Volume 241, MFCS 2022, Complete Volume}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {1--1236},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022},
URN = {urn:nbn:de:0030-drops-167975},
doi = {10.4230/LIPIcs.MFCS.2022},
annote = {Keywords: LIPIcs, Volume 241, MFCS 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{szeider_et_al:LIPIcs.MFCS.2022.0,
author = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {0:i--0:xviii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.0},
URN = {urn:nbn:de:0030-drops-167981},
doi = {10.4230/LIPIcs.MFCS.2022.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk)
Abstract
We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d > 1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a graph G with the average vertex degree D > 1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems, to decide whether a 2-connected graph contains a cycle of length at least 2d+k or of a cycle of length at least D+k, is fixed-parameter tractable parameterized by k.
Cite as
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 1:1-1:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fomin_et_al:LIPIcs.MFCS.2022.1,
author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill},
title = {{Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {1:1--1:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.1},
URN = {urn:nbn:de:0030-drops-167999},
doi = {10.4230/LIPIcs.MFCS.2022.1},
annote = {Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization, average degree, dense graph, Dirac theorem, Erd\H{o}s-Gallai theorem}
}
Document
Invited Talk
Modern Dynamic Data Structures (Invited Talk)
Abstract
We give an overview of differentially private dynamic data structure, aka differentially private algorithms under continual release.
Cite as
Monika Henzinger. Modern Dynamic Data Structures (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{henzinger:LIPIcs.MFCS.2022.2,
author = {Henzinger, Monika},
title = {{Modern Dynamic Data Structures}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {2:1--2:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.2},
URN = {urn:nbn:de:0030-drops-168009},
doi = {10.4230/LIPIcs.MFCS.2022.2},
annote = {Keywords: Differential privacy, data structures}
}
Document
Invited Talk
An Updated Survey of Bidding Games on Graphs (Invited Talk)
Abstract
A graph game is a two-player zero-sum game in which the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. In bidding games, both players have budgets, and in each turn, we hold an "auction" (bidding) to determine which player moves the token. In this survey, we consider several bidding mechanisms and their effect on the properties of the game. Specifically, bidding games, and in particular bidding games of infinite duration, have an intriguing equivalence with random-turn games in which in each turn, the player who moves is chosen randomly. We summarize how minor changes in the bidding mechanism lead to unexpected differences in the equivalence with random-turn games.
Cite as
Guy Avni and Thomas A. Henzinger. An Updated Survey of Bidding Games on Graphs (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 3:1-3:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{avni_et_al:LIPIcs.MFCS.2022.3,
author = {Avni, Guy and Henzinger, Thomas A.},
title = {{An Updated Survey of Bidding Games on Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {3:1--3:6},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.3},
URN = {urn:nbn:de:0030-drops-168017},
doi = {10.4230/LIPIcs.MFCS.2022.3},
annote = {Keywords: Bidding games, Richman bidding, poorman bidding, mean-payoff, parity}
}
Document
Invited Talk
Probabilistic Model Checking for Strategic Equilibria-Based Decision Making: Advances and Challenges (Invited Talk)
Abstract
Game-theoretic concepts have been extensively studied in economics to provide insight into competitive behaviour and strategic decision making. As computing systems increasingly involve concurrently acting autonomous agents, game-theoretic approaches are becoming widespread in computer science as a faithful modelling abstraction. These techniques can be used to reason about the competitive or collaborative behaviour of multiple rational agents with distinct goals or objectives. This paper provides an overview of recent advances in developing a modelling, verification and strategy synthesis framework for concurrent stochastic games implemented in the probabilistic model checker PRISM-games. This is based on a temporal logic that supports finite- and infinite-horizon temporal properties in both a zero-sum and nonzero-sum setting, the latter using Nash and correlated equilibria with respect to two optimality criteria, social welfare and social fairness. We summarise the key concepts, logics and algorithms and the currently available tool support. Future challenges and recent progress in adapting the framework and algorithmic solutions to continuous environments and neural networks are also outlined.
Cite as
Marta Kwiatkowska, Gethin Norman, David Parker, Gabriel Santos, and Rui Yan. Probabilistic Model Checking for Strategic Equilibria-Based Decision Making: Advances and Challenges (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kwiatkowska_et_al:LIPIcs.MFCS.2022.4,
author = {Kwiatkowska, Marta and Norman, Gethin and Parker, David and Santos, Gabriel and Yan, Rui},
title = {{Probabilistic Model Checking for Strategic Equilibria-Based Decision Making: Advances and Challenges}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {4:1--4:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.4},
URN = {urn:nbn:de:0030-drops-168026},
doi = {10.4230/LIPIcs.MFCS.2022.4},
annote = {Keywords: Probabilistic model checking, stochastic games, equilibria}
}
Document
Invited Talk
Online Bipartite Matching and Adwords (Invited Talk)
Abstract
The purpose of this paper is to give a "textbook quality" proof of the optimal algorithm, called Ranking, for the online bipartite matching problem (OBM) and to highlight its role in matching-based market design. In particular, we discuss a generalization of OBM, called the adwords problem, which has had a significant impact in the ad auctions marketplace.
Cite as
Vijay V. Vazirani. Online Bipartite Matching and Adwords (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 5:1-5:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{vazirani:LIPIcs.MFCS.2022.5,
author = {Vazirani, Vijay V.},
title = {{Online Bipartite Matching and Adwords}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {5:1--5:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.5},
URN = {urn:nbn:de:0030-drops-168031},
doi = {10.4230/LIPIcs.MFCS.2022.5},
annote = {Keywords: matching-based market design, online algorithms, ad auctions, competitive analysis}
}
Document
Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Abstract
For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V(P) is connected. An s-t path P is non-disconnecting if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t.
Cite as
Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, and Saket Saurabh. Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{abhinav_et_al:LIPIcs.MFCS.2022.6,
author = {Abhinav, Ankit and Bandopadhyay, Susobhan and Banik, Aritra and Kobayashi, Yasuaki and Nagano, Shunsuke and Otachi, Yota and Saurabh, Saket},
title = {{Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {6:1--6:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.6},
URN = {urn:nbn:de:0030-drops-168041},
doi = {10.4230/LIPIcs.MFCS.2022.6},
annote = {Keywords: Non-separating path, Parameterized complexity}
}
Document
Comonadic semantics for hybrid logic
Abstract
Hybrid logic is a widely-studied extension of basic modal logic, which corresponds to the bounded fragment of first-order logic. We study it from two novel perspectives: (1) We apply the recently introduced paradigm of comonadic semantics, which provides a new set of tools drawing on ideas from categorical semantics which can be applied to finite model theory, descriptive complexity and combinatorics. (2) We give a novel semantic characterization of hybrid logic in terms of invariance under disjoint extensions, a minimal form of locality. A notable feature of this result is that we give a uniform proof, valid for both the finite and infinite cases.
Cite as
Samson Abramsky and Dan Marsden. Comonadic semantics for hybrid logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{abramsky_et_al:LIPIcs.MFCS.2022.7,
author = {Abramsky, Samson and Marsden, Dan},
title = {{Comonadic semantics for hybrid logic}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {7:1--7:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.7},
URN = {urn:nbn:de:0030-drops-168055},
doi = {10.4230/LIPIcs.MFCS.2022.7},
annote = {Keywords: comonads, model comparison games, semantic characterizations, hybrid logic, bounded fragment}
}
Document
The Complexity of Periodic Energy Minimisation
Abstract
The computational complexity of pairwise energy minimisation of N points in real space is a long-standing open problem. The idea of the potential intractability of the problem was supported by a lack of progress in finding efficient algorithms, even when restricted the integer grid approximation. In this paper we provide a firm answer to the problem on ℤ^d by showing that for a large class of pairwise energy functions the problem of periodic energy minimisation is NP-hard if the size of the period (known as a unit cell) is fixed, and is undecidable otherwise. We do so by introducing an abstraction of pairwise average energy minimisation as a mathematical problem, which covers many existing models. The most influential aspects of this work are showing for the first time: 1) undecidability of average pairwise energy minimisation in general 2) computational hardness for the most natural model with periodic boundary conditions, and 3) novel reductions for a large class of generic pairwise energy functions covering many physical abstractions at once. In particular, we develop a new tool of overlapping digital rhombuses to incorporate the properties of the physical force fields, and we connect it with classical tiling problems. Moreover, we illustrate the power of such reductions by incorporating more physical properties such as charge neutrality, and we show an inapproximability result for the extreme case of the 1D average energy minimisation problem.
Cite as
Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, and Igor Potapov. The Complexity of Periodic Energy Minimisation. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{adamson_et_al:LIPIcs.MFCS.2022.8,
author = {Adamson, Duncan and Deligkas, Argyrios and Gusev, Vladimir V. and Potapov, Igor},
title = {{The Complexity of Periodic Energy Minimisation}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {8:1--8:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.8},
URN = {urn:nbn:de:0030-drops-168065},
doi = {10.4230/LIPIcs.MFCS.2022.8},
annote = {Keywords: Optimisation of periodic structures, tiling, undecidability, NP-hardness}
}
Document
Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
Abstract
We consider a weighted counting problem on matchings, denoted PrMatching(𝒢), on an arbitrary fixed graph family 𝒢. The input consists of a graph G ∈ 𝒢 and of rational probabilities of existence on every edge of G, assuming independence. The output is the probability of obtaining a matching of G in the resulting distribution, i.e., a set of edges that are pairwise disjoint. It is known that, if 𝒢 has bounded treewidth, then PrMatching(𝒢) can be solved in polynomial time. In this paper we show that, under some assumptions, bounded treewidth in fact characterizes the tractable graph families for this problem. More precisely, we show intractability for all graph families 𝒢 satisfying the following treewidth-constructibility requirement: given an integer k in unary, we can construct in polynomial time a graph G ∈ 𝒢 with treewidth at least k. Our hardness result is then the following: for any treewidth-constructible graph family 𝒢, the problem PrMatching(𝒢) is intractable. This generalizes known hardness results for weighted matching counting under some restrictions that do not bound treewidth, e.g., being planar, 3-regular, or bipartite; it also answers a question left open in [Amarilli et al., 2016]. We also obtain a similar lower bound for the weighted counting of edge covers.
Cite as
Antoine Amarilli and Mikaël Monet. Weighted Counting of Matchings in Unbounded-Treewidth Graph Families. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{amarilli_et_al:LIPIcs.MFCS.2022.9,
author = {Amarilli, Antoine and Monet, Mika\"{e}l},
title = {{Weighted Counting of Matchings in Unbounded-Treewidth Graph Families}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {9:1--9:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.9},
URN = {urn:nbn:de:0030-drops-168078},
doi = {10.4230/LIPIcs.MFCS.2022.9},
annote = {Keywords: Treewidth, counting complexity, matchings, Fibonacci sequence}
}
Document
On Upward-Planar L-Drawings of Graphs
Abstract
In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of e and of a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for st-graphs, i.e., planar DAGs with a single source s and a single sink t containing an edge directed from s to t. It is known that a plane st-graph, i.e., an embedded st-graph in which the edge (s,t) is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic st-ordering, which can be tested in linear time.
We study upward-planar L-drawings of DAGs that are not necessarily st-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane st-graph admitting a bitonic st-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but the DAG is biconnected and series-parallel.
Cite as
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, and Giordano Da Lozzo. On Upward-Planar L-Drawings of Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{angelini_et_al:LIPIcs.MFCS.2022.10,
author = {Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano},
title = {{On Upward-Planar L-Drawings of Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {10:1--10:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.10},
URN = {urn:nbn:de:0030-drops-168085},
doi = {10.4230/LIPIcs.MFCS.2022.10},
annote = {Keywords: graph drawing, planar L-drawings, directed graphs, bitonic st-ordering, upward planarity, series-parallel graphs}
}
Document
RAC Drawings of Graphs with Low Degree
Abstract
Motivated by cognitive experiments providing evidence that large crossing-angles do not impair the readability of a graph drawing, RAC (Right Angle Crossing) drawings were introduced to address the problem of producing readable representations of non-planar graphs by supporting the optimal case in which all crossings form 90° angles.
In this work, we make progress on the problem of finding RAC drawings of graphs of low degree. In this context, a long-standing open question asks whether all degree-3 graphs admit straight-line RAC drawings. This question has been positively answered for the Hamiltonian degree-3 graphs. We improve on this result by extending to the class of 3-edge-colorable degree-3 graphs. When each edge is allowed to have one bend, we prove that degree-4 graphs admit such RAC drawings, a result which was previously known only for degree-3 graphs. Finally, we show that 7-edge-colorable degree-7 graphs admit RAC drawings with two bends per edge. This improves over the previous result on degree-6 graphs.
Cite as
Patrizio Angelini, Michael A. Bekos, Julia Katheder, Michael Kaufmann, and Maximilian Pfister. RAC Drawings of Graphs with Low Degree. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{angelini_et_al:LIPIcs.MFCS.2022.11,
author = {Angelini, Patrizio and Bekos, Michael A. and Katheder, Julia and Kaufmann, Michael and Pfister, Maximilian},
title = {{RAC Drawings of Graphs with Low Degree}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.11},
URN = {urn:nbn:de:0030-drops-168090},
doi = {10.4230/LIPIcs.MFCS.2022.11},
annote = {Keywords: Graph Drawing, RAC graphs, Straight-line and bent drawings}
}
Document
Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs
Abstract
A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal vertex, or sink, has been reached. The ARRIVAL problem, as defined by Dohrau et al. [Dohrau et al., 2017], consists in determining which sink will be reached. While the walk itself can take an exponential number of steps, this problem belongs to the complexity class NP ∩ co-NP without being known to be in P. In this work, we define a class of directed graphs, namely tree-like multigraphs, which are multigraphs having the global shape of an undirected tree. We prove that in this class, ARRIVAL can be solved in almost linear time, while the number of steps of a rotor walk can still be exponential. Then, we give an application of this result to solve some deterministic analogs of stochastic models (e.g., Markovian decision processes, Stochastic Games).
Cite as
David Auger, Pierre Coucheney, and Loric Duhazé. Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{auger_et_al:LIPIcs.MFCS.2022.12,
author = {Auger, David and Coucheney, Pierre and Duhaz\'{e}, Loric},
title = {{Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {12:1--12:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.12},
URN = {urn:nbn:de:0030-drops-168103},
doi = {10.4230/LIPIcs.MFCS.2022.12},
annote = {Keywords: Rotor-routing, Rotor Walk, Reachability Problem, Game Theory, Tree-like Multigraph}
}
Document
Graph Realization of Distance Sets
Abstract
The Distance Realization problem is defined as follows. Given an n × n matrix D of nonnegative integers, interpreted as inter-vertex distances, find an n-vertex weighted or unweighted graph G realizing D, i.e., whose inter-vertex distances satisfy dist_G(i,j) = D_{i,j} for every 1 ≤ i < j ≤ n, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e.g., trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix D may contain a range of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most k values yields the problem k-Range Distance Realization (or k-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry D_{i,j} of the matrix may contain an arbitrary set of acceptable values for the distance between i and j, for every 1 ≤ i < j ≤ n. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most k values as k-Set Distance Realization (or k-Set-DR).
We first show that 2-Range-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. We then explore Set-DR where the realization is restricted to the families of stars, paths, or cycles. For the weighted case, our positive results are that for each of these families there exists a polynomial time algorithm for 2-Set-DR. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths and cycles. For the unweighted case, our results are the same, except for the case of unweighted stars, for which k-Set-DR is polynomially solvable for any k.
Cite as
Amotz Bar-Noy, David Peleg, Mor Perry, and Dror Rawitz. Graph Realization of Distance Sets. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{barnoy_et_al:LIPIcs.MFCS.2022.13,
author = {Bar-Noy, Amotz and Peleg, David and Perry, Mor and Rawitz, Dror},
title = {{Graph Realization of Distance Sets}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {13:1--13:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.13},
URN = {urn:nbn:de:0030-drops-168119},
doi = {10.4230/LIPIcs.MFCS.2022.13},
annote = {Keywords: Graph Realization, distance realization, network design}
}
Document
On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph
Abstract
We consider the problem of characterizing degree sequences that can be realized by a bipartite graph. If a partition of the sequence into the two sides of the bipartite graph is given as part of the input, then a complete characterization has been established over 60 years ago. However, the general question, in which a partition and a realizing graph need to be determined, is still open. We investigate the role of an important class of special partitions, called High-Low partitions, which separate the degrees of a sequence into two groups, the high degrees and the low degrees. We show that when the High-Low partition exists and satisfies some natural properties, analysing the High-Low partition resolves the bigraphic realization problem. For sequences that are known to be not realizable by a bipartite graph or that are undecided, we provide approximate realizations based on the High-Low partition.
Cite as
Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz. On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{barnoy_et_al:LIPIcs.MFCS.2022.14,
author = {Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Rawitz, Dror},
title = {{On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.14},
URN = {urn:nbn:de:0030-drops-168121},
doi = {10.4230/LIPIcs.MFCS.2022.14},
annote = {Keywords: Graph Realization, Bipartite Graphs, Degree Sequences, Graphic Sequences, Bigraphic Sequences, Approximate Realization, Multigraph Realization}
}
Document
Towards a Model Theory of Ordered Logics: Expressivity and Interpolation
Abstract
We consider the family of guarded and unguarded ordered logics, that constitute a recently rediscovered family of decidable fragments of first-order logic (FO), in which the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. While the complexities of their satisfiability problems are now well-established, their model theory, however, is poorly understood. Our paper aims to provide some insight into it.
We start by providing suitable notions of bisimulation for ordered logics. We next employ bisimulations to compare the relative expressive power of ordered logics, and to characterise our logics as bisimulation-invariant fragments of FO à la van Benthem.
Afterwards, we study the Craig Interpolation Property (CIP). We refute yet another claim from the infamous work by Purdy, by showing that the fluted and forward fragments do not enjoy CIP. We complement this result by showing that the ordered fragment and the guarded ordered logics enjoy CIP. These positive results rely on novel and quite intricate model constructions, which take full advantage of the "forwardness" of our logics.
Cite as
Bartosz Bednarczyk and Reijo Jaakkola. Towards a Model Theory of Ordered Logics: Expressivity and Interpolation. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bednarczyk_et_al:LIPIcs.MFCS.2022.15,
author = {Bednarczyk, Bartosz and Jaakkola, Reijo},
title = {{Towards a Model Theory of Ordered Logics: Expressivity and Interpolation}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {15:1--15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.15},
URN = {urn:nbn:de:0030-drops-168132},
doi = {10.4230/LIPIcs.MFCS.2022.15},
annote = {Keywords: ordered fragments, fluted fragment, guarded fragment, model theory, Craig Interpolation Property, expressive power, model checking}
}
Document
Algebraic Representations of Unique Bipartite Perfect Matching
Abstract
We obtain complete characterizations of the Unique Bipartite Perfect Matching function, and of its Boolean dual, using multilinear polynomials over the reals. Building on previous results [Beniamini, 2020; Beniamini and Nisan, 2021], we show that, surprisingly, the dual description is sparse and has low 𝓁₁-norm - only exponential in Θ(n log n), and this result extends even to other families of matching-related functions. Our approach relies on the Möbius numbers in the matching-covered lattice, and a key ingredient in our proof is Möbius' inversion formula.
These polynomial representations yield complexity-theoretic results. For instance, we show that unique bipartite matching is evasive for classical decision trees, and nearly evasive even for generalized query models. We also obtain a tight Θ(n log n) bound on the log-rank of the associated two-party communication task.
Cite as
Gal Beniamini. Algebraic Representations of Unique Bipartite Perfect Matching. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{beniamini:LIPIcs.MFCS.2022.16,
author = {Beniamini, Gal},
title = {{Algebraic Representations of Unique Bipartite Perfect Matching}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {16:1--16:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.16},
URN = {urn:nbn:de:0030-drops-168140},
doi = {10.4230/LIPIcs.MFCS.2022.16},
annote = {Keywords: Bipartite Perfect Matching, Boolean Functions, Partially Ordered Sets}
}
Document
Fixed-Point Cycles and Approximate EFX Allocations
Abstract
We study edge-labelings of the complete bidirected graph K^↔_n with functions that map the set [d] = {1, … , d} to itself. We call a directed cycle in K^↔_n a fixed-point cycle if composing the labels of its edges in order results in a map that has a fixed point, and we say that a labeling is fixed-point-free if no fixed-point cycle exists. For a given d, we ask for the largest value of n, denoted R_f(d), for which there exists a fixed-point-free labeling of K^↔_n. Determining R_f(d) for all d > 0 is a natural Ramsey-type question, generalizing some well-studied zero-sum problems in extremal combinatorics. The problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra [EC 2021], who proved that d ≤ R_f(d) ≤ d⁴+d and showed that the problem has close connections to EFX allocations, a central problem of fair allocation in social choice theory.
In this paper we show the improved bound R_f(d) ≤ d^{2 + o(1)}, yielding an efficient (1-ε)-EFX allocation with n agents and O((n/ε)^{0.67}) unallocated goods; this improves the bound of O((n/ε)^{0.8}) of Chaudhury, Garg, Mehlhorn, Mehta, and Misra.
{Additionally, we prove the stronger upper bound 2d-2, in the case where all edge-labels are permutations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of ℤ_d, was recently considered by Alon and Krivelevich [JGT 2021] and by Mészáros and Steiner [EJC 2021]. Our result improves the bounds obtained by these authors and extends them to labelings with elements of an arbitrary (not necessarily commutative) group, while also simplifying the proof.}
Cite as
Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. Fixed-Point Cycles and Approximate EFX Allocations. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{berendsohn_et_al:LIPIcs.MFCS.2022.17,
author = {Berendsohn, Benjamin Aram and Boyadzhiyska, Simona and Kozma, L\'{a}szl\'{o}},
title = {{Fixed-Point Cycles and Approximate EFX Allocations}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {17:1--17:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.17},
URN = {urn:nbn:de:0030-drops-168153},
doi = {10.4230/LIPIcs.MFCS.2022.17},
annote = {Keywords: fixed-point, zero-sum cycle, Ramsey theory, fair allocation, EFX}
}
Document
Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits
Abstract
We show that any product-depth Δ algebraic circuit for the Iterated Matrix Multiplication Polynomial IMM_{n,d} (when d = O(log n/log log n)) must be of size at least n^Ω(d^{1/(φ²)^Δ}) where φ = 1.618… is the golden ratio. This improves the recent breakthrough result of Limaye, Srinivasan and Tavenas (FOCS'21) who showed a super polynomial lower bound of the form n^Ω(d^{1/4^Δ}) for constant-depth circuits.
One crucial idea of the (LST21) result was to use set-multilinear polynomials where each of the sets in the underlying partition of the variables could be of different sizes. By picking the set sizes more carefully (depending on the depth we are working with), we first show that any product-depth Δ set-multilinear circuit for IMM_{n,d} (when d = O(log n)) needs size at least n^Ω(d^{1/φ^Δ}). This improves the n^Ω(d^{1/2^Δ}) lower bound of (LST21). We then use their Hardness Escalation technique to lift this to general circuits.
We also show that our lower bound cannot be improved significantly using these same techniques. For the specific two set sizes used in (LST21), they showed that their lower bound cannot be improved. We show that for any d^o(1) set sizes (out of maximum possible d), the scope for improving our lower bound is minuscule: there exists a set-multilinear circuit that has product-depth Δ and size almost matching our lower bound such that the value of the measure used to prove the lower bound is maximum for this circuit. This results in a barrier to further improvement using the same measure.
Cite as
C. S. Bhargav, Sagnik Dutta, and Nitin Saxena. Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bhargav_et_al:LIPIcs.MFCS.2022.18,
author = {Bhargav, C. S. and Dutta, Sagnik and Saxena, Nitin},
title = {{Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {18:1--18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.18},
URN = {urn:nbn:de:0030-drops-168161},
doi = {10.4230/LIPIcs.MFCS.2022.18},
annote = {Keywords: polynomials, lower bounds, algebraic circuits, proof barrier, fibonacci numbers}
}
Document
Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs
Abstract
A Conflict-Free Open Neighborhood coloring, abbreviated CFON^* coloring, of a graph G = (V,E) using k colors is an assignment of colors from a set of k colors to a subset of vertices of V(G) such that every vertex sees some color exactly once in its open neighborhood. The minimum k for which G has a CFON^* coloring using k colors is called the CFON^* chromatic number of G, denoted by χ_{ON}^*(G). The analogous notion for closed neighborhood is called CFCN^* coloring and the analogous parameter is denoted by χ_{CN}^*(G). The problem of deciding whether a given graph admits a CFON^* (or CFCN^*) coloring that uses k colors is NP-complete. Below, we describe briefly the main results of this paper.
- For k ≥ 3, we show that if G is a K_{1,k}-free graph then χ_{ON}^*(G) = O(k²log Δ), where Δ denotes the maximum degree of G. Dębski and Przybyło in [J. Graph Theory, 2021] had shown that if G is a line graph, then χ_{CN}^*(G) = O(log Δ). As an open question, they had asked if their result could be extended to claw-free (K_{1,3}-free) graphs, which are a superclass of line graphs. Since it is known that the CFCN^* chromatic number of a graph is at most twice its CFON^* chromatic number, our result positively answers the open question posed by Dębski and Przybyło.
- We show that if the minimum degree of any vertex in G is Ω(Δ/{log^ε Δ}) for some ε ≥ 0, then χ_{ON}^*(G) = O(log^{1+ε}Δ). This is a generalization of the result given by Dębski and Przybyło in the same paper where they showed that if the minimum degree of any vertex in G is Ω(Δ), then χ_{ON}^*(G)= O(logΔ).
- We give a polynomial time algorithm to compute χ_{ON}^*(G) for interval graphs G. This answers in positive the open question posed by Reddy [Theoretical Comp. Science, 2018] to determine whether the CFON^* chromatic number can be computed in polynomial time on interval graphs.
- We explore biconvex graphs, a subclass of bipartite graphs and give a polynomial time algorithm to compute their CFON^* chromatic number. This is interesting as Abel et al. [SIDMA, 2018] had shown that it is NP-complete to decide whether a planar bipartite graph G has χ_{ON}^*(G) = k where k ∈ {1, 2, 3}.
Cite as
Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, and Rogers Mathew. Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bhyravarapu_et_al:LIPIcs.MFCS.2022.19,
author = {Bhyravarapu, Sriram and Kalyanasundaram, Subrahmanyam and Mathew, Rogers},
title = {{Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {19:1--19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.19},
URN = {urn:nbn:de:0030-drops-168173},
doi = {10.4230/LIPIcs.MFCS.2022.19},
annote = {Keywords: Conflict-free coloring, Interval graphs, Bipartite graphs, Claw-free graphs}
}
Document
Skolem Meets Schanuel
Abstract
The celebrated Skolem-Mahler-Lech Theorem states that the set of zeros of a linear recurrence sequence is the union of a finite set and finitely many arithmetic progressions. The corresponding computational question, the Skolem Problem, asks to determine whether a given linear recurrence sequence has a zero term. Although the Skolem-Mahler-Lech Theorem is almost 90 years old, decidability of the Skolem Problem remains open. The main contribution of this paper is an algorithm to solve the Skolem Problem for simple linear recurrence sequences (those with simple characteristic roots). Whenever the algorithm terminates, it produces a stand-alone certificate that its output is correct - a set of zeros together with a collection of witnesses that no further zeros exist. We give a proof that the algorithm always terminates assuming two classical number-theoretic conjectures: the Skolem Conjecture (also known as the Exponential Local-Global Principle) and the p-adic Schanuel Conjecture. Preliminary experiments with an implementation of this algorithm within the tool Skolem point to the practical applicability of this method.
Cite as
Yuri Bilu, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, and James Worrell. Skolem Meets Schanuel. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bilu_et_al:LIPIcs.MFCS.2022.20,
author = {Bilu, Yuri and Luca, Florian and Nieuwveld, Joris and Ouaknine, Jo\"{e}l and Purser, David and Worrell, James},
title = {{Skolem Meets Schanuel}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {20:1--20:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.20},
URN = {urn:nbn:de:0030-drops-168180},
doi = {10.4230/LIPIcs.MFCS.2022.20},
annote = {Keywords: Skolem Problem, Skolem Conjecture, Exponential Local-Global Principle, p-adic Schanuel Conjecture}
}
Document
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
Abstract
When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of "similarity" between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard.
Cite as
Niclas Boehmer, Klaus Heeger, and Rolf Niedermeier. Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{boehmer_et_al:LIPIcs.MFCS.2022.21,
author = {Boehmer, Niclas and Heeger, Klaus and Niedermeier, Rolf},
title = {{Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.21},
URN = {urn:nbn:de:0030-drops-168194},
doi = {10.4230/LIPIcs.MFCS.2022.21},
annote = {Keywords: Stable Marriage, Stable Roommates, adapting to changing preferences, NP-hardness, W\lbrack1\rbrack-hardness, XP, FPT, master lists, incremental algorithms}
}
Document
Tree Exploration in Dual-Memory Model
Abstract
We study the problem of online tree exploration by a deterministic mobile agent. Our main objective is to establish what features of the model of the mobile agent and the environment allow linear exploration time. We study agents that, upon entering a node, do not receive as input the edge via which they entered. In such model, deterministic memoryless exploration is infeasible, hence the agent needs to be allowed to use some memory. The memory can be located at the agent or at each node. The existing lower bounds show that if the memory is either only at the agent or only at the nodes, then the exploration needs superlinear time. We show that tree exploration in dual-memory model, with constant memory at the agent and logarithmic in the degree at each node is possible in linear time when one of the two additional features is present: fixed initial state of the memory at each node (so called clean memory) or a single movable token. We present two algorithms working in linear time for arbitrary trees in these two models. On the other hand, in our lower bound we show that if the agent has a single bit of memory and one bit is present at each node, then the exploration may require quadratic time even on paths, if the initial memory at nodes could be set arbitrarily (so called dirty memory). This shows that having clean node memory or a token allows linear time exploration of trees in the dual-memory model, but having neither of those features may lead to quadratic exploration time even on a simple path.
Cite as
Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pająk. Tree Exploration in Dual-Memory Model. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bojko_et_al:LIPIcs.MFCS.2022.22,
author = {Bojko, Dominik and Gotfryd, Karol and Kowalski, Dariusz R. and Paj\k{a}k, Dominik},
title = {{Tree Exploration in Dual-Memory Model}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {22:1--22:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.22},
URN = {urn:nbn:de:0030-drops-168207},
doi = {10.4230/LIPIcs.MFCS.2022.22},
annote = {Keywords: Graph exploration, agent, memory, tree, deterministic algorithms, lower bound}
}
Document
On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares
Abstract
Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.
Cite as
Ilario Bonacina, Nicola Galesi, and Massimo Lauria. On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bonacina_et_al:LIPIcs.MFCS.2022.23,
author = {Bonacina, Ilario and Galesi, Nicola and Lauria, Massimo},
title = {{On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {23:1--23:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.23},
URN = {urn:nbn:de:0030-drops-168211},
doi = {10.4230/LIPIcs.MFCS.2022.23},
annote = {Keywords: polynomial calculus, sum-of-squares, roots of unity, knapsack}
}
Document
Complete ZX-Calculi for the Stabiliser Fragment in Odd Prime Dimensions
Abstract
We introduce a family of ZX-calculi which axiomatise the stabiliser fragment of quantum theory in odd prime dimensions. These calculi recover many of the nice features of the qubit ZX-calculus which were lost in previous proposals for higher-dimensional systems. We then prove that these calculi are complete, i.e. provide a set of rewrite rules which can be used to prove any equality of stabiliser quantum operations. Adding a discard construction, we obtain a calculus complete for mixed state stabiliser quantum mechanics in odd prime dimensions, and this furthermore gives a complete axiomatisation for the related diagrammatic language for affine co-isotropic relations.
Cite as
Robert I. Booth and Titouan Carette. Complete ZX-Calculi for the Stabiliser Fragment in Odd Prime Dimensions. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{booth_et_al:LIPIcs.MFCS.2022.24,
author = {Booth, Robert I. and Carette, Titouan},
title = {{Complete ZX-Calculi for the Stabiliser Fragment in Odd Prime Dimensions}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {24:1--24:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.24},
URN = {urn:nbn:de:0030-drops-168225},
doi = {10.4230/LIPIcs.MFCS.2022.24},
annote = {Keywords: ZX-calculus, completeness, quantum, stabiliser, qudits}
}
Document
Extending Partial Representations of Circle Graphs in Near-Linear Time
Abstract
The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph H ⊆ G and a representation H of H. The question is whether G admits a representation G whose restriction to H is H. We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams.
We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in O((n + m) α(n + m)) time, where α is the inverse Ackermann function. This improves over an O(n³)-time algorithm by Chaplick, Fulek and Klavík [2019]. The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.
Cite as
Guido Brückner, Ignaz Rutter, and Peter Stumpf. Extending Partial Representations of Circle Graphs in Near-Linear Time. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bruckner_et_al:LIPIcs.MFCS.2022.25,
author = {Br\"{u}ckner, Guido and Rutter, Ignaz and Stumpf, Peter},
title = {{Extending Partial Representations of Circle Graphs in Near-Linear Time}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {25:1--25:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.25},
URN = {urn:nbn:de:0030-drops-168233},
doi = {10.4230/LIPIcs.MFCS.2022.25},
annote = {Keywords: circle graphs, partial representation extension, split decomposition tree, recognition algorithm}
}
Document
Boundaries to Single-Agent Stability in Additively Separable Hedonic Games
Abstract
Coalition formation considers the question of how to partition a set of agents into coalitions with respect to their preferences. Additively separable hedonic games (ASHGs) are a dominant model where cardinal single-agent values are aggregated into preferences by taking sums. Output partitions are typically measured by means of stability, and we follow this approach by considering stability based on single-agent movements (to join other coalitions), where a coalition is defined as stable if there exists no beneficial single-agent deviation. Permissible deviations should always lead to an improvement for the deviator, but they may also be constrained by demanding the consent of agents involved in the deviations, i.e., by agents in the abandoned or welcoming coalition. Most of the existing research focuses on the unanimous consent of one or both of these coalitions, but more recent research relaxes this to majority-based consent. Our contribution is twofold. First, we settle the computational complexity of the existence of contractually Nash stable partitions, where deviations are constrained by the unanimous consent of the abandoned coalition. This resolves the complexity of the last classical stability notion for ASHGs. Second, we identify clear boundaries to the tractability of stable partitions under majority-based stability concepts by proving elaborate hardness results for restricted classes of ASHGs. Slight further restrictions lead to positive results.
Cite as
Martin Bullinger. Boundaries to Single-Agent Stability in Additively Separable Hedonic Games. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bullinger:LIPIcs.MFCS.2022.26,
author = {Bullinger, Martin},
title = {{Boundaries to Single-Agent Stability in Additively Separable Hedonic Games}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {26:1--26:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.26},
URN = {urn:nbn:de:0030-drops-168249},
doi = {10.4230/LIPIcs.MFCS.2022.26},
annote = {Keywords: Coalition Formation, Hedonic Games, Stability}
}
Document
Bounded Degree Nonnegative Counting CSP
Abstract
Constraint satisfaction problems (CSP) encompass an enormous variety of computational problems. In particular, all partition functions from statistical physics, such as spin systems, are special cases of counting CSP (#CSP). We prove a complete complexity classification for every counting problem in #CSP with nonnegative valued constraint functions that is valid when every variable occurs a bounded number of times in all constraints. We show that, depending on the set of constraint functions ℱ, every problem in the complexity class #CSP(ℱ) defined by ℱ is either polynomial time computable for all instances without the bounded occurrence restriction, or is #P-hard even when restricted to bounded degree input instances. The constant bound in the degree depends on ℱ. The dichotomy criterion on ℱ is decidable. As a second contribution, we prove a slightly modified but more streamlined decision procedure (from [Jin-Yi Cai et al., 2011]) for tractability. This enables us to fully classify a family of directed weighted graph homomorphism problems. This family contains both P-time tractable problems and #P-hard problems. To our best knowledge, this is the first family of such problems explicitly classified that are not acyclic, thereby the Lovász-goodness criterion of Dyer-Goldberg-Paterson [Martin E. Dyer et al., 2006] cannot be applied.
Cite as
Jin-Yi Cai and Daniel P. Szabo. Bounded Degree Nonnegative Counting CSP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{cai_et_al:LIPIcs.MFCS.2022.27,
author = {Cai, Jin-Yi and Szabo, Daniel P.},
title = {{Bounded Degree Nonnegative Counting CSP}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {27:1--27:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.27},
URN = {urn:nbn:de:0030-drops-168250},
doi = {10.4230/LIPIcs.MFCS.2022.27},
annote = {Keywords: Computational Counting Complexity, Constraint Satisfaction Problems, Counting CSPs, Complexity Dichotomy, Nonnegative Counting CSP, Graph Homomorphisms}
}
Document
Continuous Rational Functions Are Deterministic Regular
Abstract
A word-to-word function is rational if it can be realized by a non-deterministic one-way transducer. Over finite words, it is a classical result that any rational function is regular, i.e. it can be computed by a deterministic two-way transducer, or equivalently, by a deterministic streaming string transducer (a one-way automaton which manipulates string registers).
This result no longer holds for infinite words, since a non-deterministic one-way transducer can guess, and check along its run, properties such as infinitely many occurrences of some pattern, which is impossible for a deterministic machine. In this paper, we identify the class of rational functions over infinite words which are also computable by a deterministic two-way transducer. It coincides with the class of rational functions which are continuous, and this property can thus be decided. This solves an open question raised in a previous paper of Dave et al.
Cite as
Olivier Carton and Gaëtan Douéneau-Tabot. Continuous Rational Functions Are Deterministic Regular. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{carton_et_al:LIPIcs.MFCS.2022.28,
author = {Carton, Olivier and Dou\'{e}neau-Tabot, Ga\"{e}tan},
title = {{Continuous Rational Functions Are Deterministic Regular}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {28:1--28:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.28},
URN = {urn:nbn:de:0030-drops-168268},
doi = {10.4230/LIPIcs.MFCS.2022.28},
annote = {Keywords: infinite words, rational functions, determinization, continuity, streaming string transducers, two-way transducers}
}
Document
On Kernels for d-Path Vertex Cover
Abstract
In this paper we study the kernelization of the d-Path Vertex Cover (d-PVC) problem. Given a graph G, the problem requires finding whether there exists a set of at most k vertices whose removal from G results in a graph that does not contain a path (not necessarily induced) with d vertices. It is known that d-PVC is NP-complete for d ≥ 2. Since the problem generalizes to d-Hitting Set, it is known to admit a kernel with 𝒪(dk^d) edges. We improve on this by giving better kernels. Specifically, we give kernels with 𝒪(k²) vertices and edges for the cases when d = 4 and d = 5. Further, we give a kernel with 𝒪(k⁴d^{2d+9}) vertices and edges for general d.
Cite as
Radovan Červený, Pratibha Choudhary, and Ondřej Suchý. On Kernels for d-Path Vertex Cover. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{cerveny_et_al:LIPIcs.MFCS.2022.29,
author = {\v{C}erven\'{y}, Radovan and Choudhary, Pratibha and Such\'{y}, Ond\v{r}ej},
title = {{On Kernels for d-Path Vertex Cover}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {29:1--29:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.29},
URN = {urn:nbn:de:0030-drops-168279},
doi = {10.4230/LIPIcs.MFCS.2022.29},
annote = {Keywords: Parameterized complexity, Kernelization, d-Hitting Set, d-Path Vertex Cover, Expansion Lemma}
}
Document
On Synthesizing Computable Skolem Functions for First Order Logic
Abstract
Skolem functions play a central role in the study of first order logic, both from theoretical and practical perspectives. While every Skolemized formula in first-order logic makes use of Skolem constants and/or functions, not all such Skolem constants and/or functions admit effectively computable interpretations. Indeed, the question of whether there exists an effectively computable interpretation of a Skolem function, and if so, how to automatically synthesize it, is fundamental to their use in several applications, such as planning, strategy synthesis, program synthesis etc.
In this paper, we investigate the computability of Skolem functions and their automated synthesis in the full generality of first order logic. We first show a strong negative result, that even under mild assumptions on the vocabulary, it is impossible to obtain computable interpretations of Skolem functions. We then show a positive result, providing a precise characterization of first-order theories that admit effective interpretations of Skolem functions, and also present algorithms to automatically synthesize such interpretations. We discuss applications of our characterization as well as complexity bounds for Skolem functions (interpreted as Turing machines).
Cite as
Supratik Chakraborty and S. Akshay. On Synthesizing Computable Skolem Functions for First Order Logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chakraborty_et_al:LIPIcs.MFCS.2022.30,
author = {Chakraborty, Supratik and Akshay, S.},
title = {{On Synthesizing Computable Skolem Functions for First Order Logic}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {30:1--30:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.30},
URN = {urn:nbn:de:0030-drops-168285},
doi = {10.4230/LIPIcs.MFCS.2022.30},
annote = {Keywords: Skolem functions, Automated, Synthesis, First order logic, Computability}
}
Document
Sample Compression Schemes for Balls in Graphs
Abstract
One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs.
Cite as
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample Compression Schemes for Balls in Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chalopin_et_al:LIPIcs.MFCS.2022.31,
author = {Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Mc Inerney, Fionn and Ratel, S\'{e}bastien and Vax\`{e}s, Yann},
title = {{Sample Compression Schemes for Balls in Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {31:1--31:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.31},
URN = {urn:nbn:de:0030-drops-168298},
doi = {10.4230/LIPIcs.MFCS.2022.31},
annote = {Keywords: Proper Sample Compression Schemes, Balls, Graphs, VC-dimension}
}
Document
On Algorithms Based on Finitely Many Homomorphism Counts
Abstract
It is well known [L. Lovász, 1967] that up to isomorphism a graph G is determined by the homomorphism counts hom(F, G), i.e., by the number of homomorphisms from F to G where F ranges over all graphs. Moreover, it suffices that F ranges over the graphs with at most as many vertices as G. Thus, in principle, we can answer any query concerning G with only accessing the hom(⋅, G)’s instead of G itself. In this paper, we deal with queries for which there is a hom algorithm, i.e., there are finitely many graphs F₁, …, F_k such that for any graph G whether it is a Yes-instance of the query is already determined by the vector hom^⟶_{F₁, …, F_k}(G): = (hom(F₁, G), …, hom(F_k, G)).
We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. On the other hand, queries expressible as a Boolean combination of universal sentences in first-order logic FO have a hom algorithm. Even though it is not easy to find FO definable queries without a hom algorithm, we succeed to show this for the non-existence of an isolated vertex, a property expressible by the FO sentence ∀ x∃ y Exy, somehow the "simplest" graph property not definable by a Boolean combination of universal sentences. These results provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm.
For adaptive hom algorithms, i.e., algorithms that might access a hom(F_{i+1}, G) with F_{i+1} depending on hom(F_j, G) for 1 ≤ j ≤ i we show that three homomorphism counts hom(⋅, G) are sufficient and in general necessary to determine the (isomorphism type of) G. In particular, by three adaptive queries we can answer any question on G. Moreover, adaptively accessing two hom(⋅, G)’s is already enough to detect an isolated vertex.
In 1993 Chaudhuri and Vardi [S. Chaudhuri and M. Y. Vardi, 1993] showed the analogue of the Lovász Isomorphism Theorem for the right homomorphism vector of a graph G, i.e, the vector of values hom(G,F) where F ranges over all graphs characterizes the isomorphism type of G. We study to what extent our results carry over to the right homomorphism vector.
Cite as
Yijia Chen, Jörg Flum, Mingjun Liu, and Zhiyang Xun. On Algorithms Based on Finitely Many Homomorphism Counts. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.MFCS.2022.32,
author = {Chen, Yijia and Flum, J\"{o}rg and Liu, Mingjun and Xun, Zhiyang},
title = {{On Algorithms Based on Finitely Many Homomorphism Counts}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {32:1--32:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.32},
URN = {urn:nbn:de:0030-drops-168301},
doi = {10.4230/LIPIcs.MFCS.2022.32},
annote = {Keywords: homomorphism numbers, hom algorithms, adaptive hom algorithms}
}
Document
Higher-Order Quantified Boolean Satisfiability
Abstract
The Boolean satisfiability problem plays a central role in computational complexity and is often used as a starting point for showing NP lower bounds. Generalisations such as Succinct SAT, where a Boolean formula is succinctly represented as a Boolean circuit, have been studied in the literature in order to lift the Boolean satisfiability problem to higher complexity classes such as NEXP. While, in theory, iterating this approach yields complete problems for k-NEXP for all k > 0, using such iterations of Succinct SAT is at best tedious when it comes to proving lower bounds.
The main contribution of this paper is to show that the Boolean satisfiability problem has another canonical generalisation in terms of higher-order Boolean functions that is arguably more suitable for showing lower bounds beyond NP. We introduce a family of problems HOSAT(k,d), k ≥ 0, d ≥ 1, in which variables are interpreted as Boolean functions of order at most k and there are d quantifier alternations between functions of order exactly k. We show that the unbounded HOSAT problem is TOWER-complete, and that HOSAT(k,d) is complete for the weak k-EXP hierarchy with d alternations for fixed k,d ≥ 1 and d odd.
We illustrate the usefulness of HOSAT by characterising the complexity of weak Presburger arithmetic, the first-order theory of the integers with addition and equality but without order. It has been a long-standing open problem whether weak Presburger arithmetic has the same complexity as standard Presburger arithmetic. We answer this question affirmatively, even for the negation-free fragment and the Horn fragment of weak Presburger arithmetic.
Cite as
Dmitry Chistikov, Christoph Haase, Zahra Hadizadeh, and Alessio Mansutti. Higher-Order Quantified Boolean Satisfiability. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{chistikov_et_al:LIPIcs.MFCS.2022.33,
author = {Chistikov, Dmitry and Haase, Christoph and Hadizadeh, Zahra and Mansutti, Alessio},
title = {{Higher-Order Quantified Boolean Satisfiability}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {33:1--33:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.33},
URN = {urn:nbn:de:0030-drops-168313},
doi = {10.4230/LIPIcs.MFCS.2022.33},
annote = {Keywords: Boolean satisfiability problem, higher-order Boolean functions, weak k-EXP hierarchies, non-elementary complexity, Presburger arithmetic}
}
Document
On Dynamic α + 1 Arboricity Decomposition and Out-Orientation
Abstract
A graph has arboricity α if its edges can be partitioned into α forests. The dynamic arboricity decomposition problem is to update a partitioning of the graph’s edges into forests, as a graph undergoes insertions and deletions of edges. We present an algorithm for maintaining partitioning into α+1 forests, provided the arboricity of the dynamic graph never exceeds α. Our algorithm has an update time of Õ(n^{3/4}) when α is at most polylogarithmic in n.
Similarly, the dynamic bounded out-orientation problem is to orient the edges of the graph such that the out-degree of each vertex is at all times bounded. For this problem, we give an algorithm that orients the edges such that the out-degree is at all times bounded by α+1, with an update time of Õ(n^{5/7}), when α is at most polylogarithmic in n. Here, the choice of α+1 should be viewed in the light of the well-known lower bound by Brodal and Fagerberg which establishes that, for general graphs, maintaining only α out-edges would require linear update time.
However, the lower bound by Brodal and Fagerberg is non-planar. In this paper, we give a lower bound showing that even for planar graphs, linear update time is needed in order to maintain an explicit three-out-orientation. For planar graphs, we show that the dynamic four forest decomposition and four-out-orientations, can be updated in Õ(n^{1/2}) time.
Cite as
Aleksander B. G. Christiansen, Jacob Holm, Eva Rotenberg, and Carsten Thomassen. On Dynamic α + 1 Arboricity Decomposition and Out-Orientation. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{christiansen_et_al:LIPIcs.MFCS.2022.34,
author = {Christiansen, Aleksander B. G. and Holm, Jacob and Rotenberg, Eva and Thomassen, Carsten},
title = {{On Dynamic \alpha + 1 Arboricity Decomposition and Out-Orientation}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {34:1--34:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.34},
URN = {urn:nbn:de:0030-drops-168320},
doi = {10.4230/LIPIcs.MFCS.2022.34},
annote = {Keywords: Dynamic graphs, bounded arboricity, data structures}
}
Document
LO_v-Calculus: A Graphical Language for Linear Optical Quantum Circuits
Abstract
We introduce the LO_v-calculus, a graphical language for reasoning about linear optical quantum circuits with so-called vacuum state auxiliary inputs. We present the axiomatics of the language and prove its soundness and completeness: two LO_v-circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the LO_v-calculus. We give a confluent and terminating rewrite system to rewrite any polarisation-preserving LO_v-circuit into a unique triangular normal form, inspired by the universal decomposition of Reck et al. (1994) for linear optical quantum circuits.
Cite as
Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix, and Benoît Valiron. LO_v-Calculus: A Graphical Language for Linear Optical Quantum Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{clement_et_al:LIPIcs.MFCS.2022.35,
author = {Cl\'{e}ment, Alexandre and Heurtel, Nicolas and Mansfield, Shane and Perdrix, Simon and Valiron, Beno\^{i}t},
title = {{LO\underlinev-Calculus: A Graphical Language for Linear Optical Quantum Circuits}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {35:1--35:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.35},
URN = {urn:nbn:de:0030-drops-168334},
doi = {10.4230/LIPIcs.MFCS.2022.35},
annote = {Keywords: Quantum Computing, Graphical Language, Linear Optical Circuits, Linear Optical Quantum Computing, Completeness}
}
Document
Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-Calculus
Abstract
Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. For instance, the complexity of implementing the permutation of some given unitary transformations can be strictly decreased by allowing coherent control, rather than using the standard quantum circuit model. In this paper, we address the problem of optimising the resources of coherently controlled quantum computations. We refine the PBS-calculus, a graphical language for coherent control which is inspired by quantum optics. In order to obtain a more resource-sensitive language, it manipulates abstract gates - that can be interpreted as queries to an oracle - and more importantly, it avoids the representation of useless wires by allowing unsaturated polarising beam splitters. Technically the language forms a coloured PROP. The language is equipped with an equational theory that we show to be sound, complete, and minimal.
Regarding resource optimisation, we introduce an efficient procedure to minimise the number of oracle queries of a given diagram. We also consider the problem of minimising both the number of oracle queries and the number of polarising beam splitters. We show that this optimisation problem is NP-hard in general, but introduce an efficient heuristic that produces optimal diagrams when at most one query to each oracle is required.
Cite as
Alexandre Clément and Simon Perdrix. Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-Calculus. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{clement_et_al:LIPIcs.MFCS.2022.36,
author = {Cl\'{e}ment, Alexandre and Perdrix, Simon},
title = {{Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-Calculus}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {36:1--36:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.36},
URN = {urn:nbn:de:0030-drops-168348},
doi = {10.4230/LIPIcs.MFCS.2022.36},
annote = {Keywords: Quantum computing, Graphical language, Coherent control, Completeness, Resource optimisation, NP-hardness}
}
Document
A Complexity Approach to Tree Algebras: the Polynomial Case
Abstract
In this paper, we consider infinitely sorted tree algebras recognising regular language of finite trees. We pursue their analysis under the angle of their asymptotic complexity, i.e. the asymptotic size of the sorts as a function of the number of variables involved.
Our main result establishes an equivalence between the languages recognised by algebras of polynomial complexity and the languages that can be described by nominal word automata that parse linearisation of the trees. On the way, we show that for such algebras, having polynomial complexity corresponds to having uniformly boundedly many orbits under permutation of the variables, or having a notion of bounded support (in a sense similar to the one in nominal sets).
We also show that being recognisable by an algebra of polynomial complexity is a decidable property for a regular language of trees.
Cite as
Thomas Colcombet and Arthur Jaquard. A Complexity Approach to Tree Algebras: the Polynomial Case. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{colcombet_et_al:LIPIcs.MFCS.2022.37,
author = {Colcombet, Thomas and Jaquard, Arthur},
title = {{A Complexity Approach to Tree Algebras: the Polynomial Case}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {37:1--37:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.37},
URN = {urn:nbn:de:0030-drops-168357},
doi = {10.4230/LIPIcs.MFCS.2022.37},
annote = {Keywords: Tree algebra, nominal automata, language theory}
}
Document
Enumeration Classes Defined by Circuits
Abstract
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.
Cite as
Nadia Creignou, Arnaud Durand, and Heribert Vollmer. Enumeration Classes Defined by Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{creignou_et_al:LIPIcs.MFCS.2022.38,
author = {Creignou, Nadia and Durand, Arnaud and Vollmer, Heribert},
title = {{Enumeration Classes Defined by Circuits}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {38:1--38:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.38},
URN = {urn:nbn:de:0030-drops-168364},
doi = {10.4230/LIPIcs.MFCS.2022.38},
annote = {Keywords: Computational complexity, enumeration problem, Boolean circuit}
}
Document
Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
Abstract
We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for every orbit of a rational matrix to escape a compact semialgebraic set defined over rational data. Our bound is doubly exponential in the ambient dimension, singly exponential in the degrees of the polynomials used to define the semialgebraic set, and singly exponential in the bitsize of the coefficients of these polynomials and the bitsize of the matrix entries. We show that our bound is tight by providing a matching lower bound.
Cite as
Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell. Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dcosta_et_al:LIPIcs.MFCS.2022.39,
author = {D'Costa, Julian and Lefaucheux, Engel and Neumann, Eike and Ouaknine, Jo\"{e}l and Worrell, James},
title = {{Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {39:1--39:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.39},
URN = {urn:nbn:de:0030-drops-168374},
doi = {10.4230/LIPIcs.MFCS.2022.39},
annote = {Keywords: Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Uniform termination bounds}
}
Document
The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems
Abstract
We study fundamental reachability problems on pseudo-orbits of linear dynamical systems. Pseudo-orbits can be viewed as a model of computation with limited precision and pseudo-reachability can be thought of as a robust version of classical reachability. Using an approach based on o-minimality of ℝ_exp we prove decidability of the discrete-time pseudo-reachability problem with arbitrary semialgebraic targets for diagonalisable linear dynamical systems. We also show that our method can be used to reduce the continuous-time pseudo-reachability problem to the (classical) time-bounded reachability problem, which is known to be conditionally decidable.
Cite as
Julian D'Costa, Toghrul Karimov, Rupak Majumdar, Joël Ouaknine, Mahmoud Salamati, and James Worrell. The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dcosta_et_al:LIPIcs.MFCS.2022.40,
author = {D'Costa, Julian and Karimov, Toghrul and Majumdar, Rupak and Ouaknine, Jo\"{e}l and Salamati, Mahmoud and Worrell, James},
title = {{The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {40:1--40:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.40},
URN = {urn:nbn:de:0030-drops-168380},
doi = {10.4230/LIPIcs.MFCS.2022.40},
annote = {Keywords: pseudo-orbits, Orbit problem, Skolem problem, linear dynamical systems, reachability}
}
Document
New Lower Bounds and Upper Bounds for Listing Avoidable Vertices
Abstract
We consider the problem of listing all avoidable vertices in a given n vertex graph. A vertex is avoidable if every pair of its neighbors is connected by a path whose internal vertices are not neighbors of the vertex or the vertex itself. Recently, Papadopolous and Zisis showed that one can list all avoidable vertices in O(n^{ω+1}) time, where ω < 2.373 is the square matrix multiplication exponent, and conjectured that a faster algorithm is not possible.
In this paper we show that under the 3-OV Hypothesis, and thus the Strong Exponential Time Hypothesis, n^{3-o(1)} time is needed to list all avoidable vertices, and thus the current best algorithm is conditionally optimal if ω = 2. We then show that if ω > 2, one can obtain an improved algorithm that for the current value of ω runs in O(n^3.32) time. We also show that our conditional lower bound is actually higher and supercubic, under a natural High Dimensional 3-OV hypothesis, implying that for our current knowledge of rectangular matrix multiplication, the avoidable vertex listing problem likely requires Ω(n^3.25) time. We obtain further algorithmic improvements for sparse graphs and bounded degree graphs.
Cite as
Mingyang Deng, Virginia Vassilevska Williams, and Ziqian Zhong. New Lower Bounds and Upper Bounds for Listing Avoidable Vertices. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{deng_et_al:LIPIcs.MFCS.2022.41,
author = {Deng, Mingyang and Vassilevska Williams, Virginia and Zhong, Ziqian},
title = {{New Lower Bounds and Upper Bounds for Listing Avoidable Vertices}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {41:1--41:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.41},
URN = {urn:nbn:de:0030-drops-168392},
doi = {10.4230/LIPIcs.MFCS.2022.41},
annote = {Keywords: Avoidable Vertex, Fine-Grained Complexity}
}
Document
Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
Abstract
We consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards the target. The goal of the algorithm is to find a strategy that minimizes the worst-case total cost. We propose a constant-factor approximation algorithm for trees with a monotonic cost function. Such function is defined as follows: there exists a vertex r such that for any two vertices u,v on any path connecting r with a leaf it holds that if u is closer to r than v, then ω(u) ≥ ω(v). The best known approximation algorithm for general weight functions has the ratio of O{√{log n}} [Dereniowski et al. ICALP 2017] and it remains as a challenging open question whether constant-factor approximation is achievable in such case. This gives our first motivation towards considering monotonic cost functions and the second one lies in the potential applications.
Cite as
Dariusz Dereniowski and Izajasz Wrosz. Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dereniowski_et_al:LIPIcs.MFCS.2022.42,
author = {Dereniowski, Dariusz and Wrosz, Izajasz},
title = {{Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {42:1--42:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.42},
URN = {urn:nbn:de:0030-drops-168405},
doi = {10.4230/LIPIcs.MFCS.2022.42},
annote = {Keywords: binary search, graph search, approximation algorithm, query complexity}
}
Document
On the Identity Problem for Unitriangular Matrices of Dimension Four
Abstract
We show that the Identity Problem is decidable in polynomial time for finitely generated sub-semigroups of the group UT(4, ℤ) of 4 × 4 unitriangular integer matrices. As a byproduct of our proof, we also show the polynomial-time decidability of several subset reachability problems in UT(4, ℤ).
Cite as
Ruiwen Dong. On the Identity Problem for Unitriangular Matrices of Dimension Four. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dong:LIPIcs.MFCS.2022.43,
author = {Dong, Ruiwen},
title = {{On the Identity Problem for Unitriangular Matrices of Dimension Four}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {43:1--43:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.43},
URN = {urn:nbn:de:0030-drops-168415},
doi = {10.4230/LIPIcs.MFCS.2022.43},
annote = {Keywords: identity problem, matrix semigroups, unitriangular matrices}
}
Document
Regular Monoidal Languages
Abstract
We introduce regular languages of morphisms in free monoidal categories, with their associated grammars and automata. These subsume the classical theory of regular languages of words and trees, but also open up a much wider class of languages over string diagrams. We use the algebra of monoidal categories to investigate the properties of regular monoidal languages, and provide sufficient conditions for their recognizability by deterministic monoidal automata.
Cite as
Matthew Earnshaw and Paweł Sobociński. Regular Monoidal Languages. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{earnshaw_et_al:LIPIcs.MFCS.2022.44,
author = {Earnshaw, Matthew and Soboci\'{n}ski, Pawe{\l}},
title = {{Regular Monoidal Languages}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.44},
URN = {urn:nbn:de:0030-drops-168425},
doi = {10.4230/LIPIcs.MFCS.2022.44},
annote = {Keywords: monoidal categories, string diagrams, formal language theory, cartesian restriction categories}
}
Document
Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP
Abstract
We construct an oracle relative to which P = NP ∩ coNP, but there are no many-one complete sets in UP, no many-one complete disjoint NP-pairs, and no many-one complete disjoint coNP-pairs.
This contributes to a research program initiated by Pudlák [P. Pudlák, 2017], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that NP ∩ coNP is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.
Cite as
Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer. Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ehrmanntraut_et_al:LIPIcs.MFCS.2022.45,
author = {Ehrmanntraut, Anton and Egidy, Fabian and Gla{\ss}er, Christian},
title = {{Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {45:1--45:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.45},
URN = {urn:nbn:de:0030-drops-168435},
doi = {10.4230/LIPIcs.MFCS.2022.45},
annote = {Keywords: computational complexity, promise classes, proof complexity, complete sets, oracle construction}
}
Document
Exact Matching in Graphs of Bounded Independence Number
Abstract
In the Exact Matching Problem (EM), we are given a graph equipped with a fixed coloring of its edges with two colors (red and blue), as well as a positive integer k. The task is then to decide whether the given graph contains a perfect matching exactly k of whose edges have color red. EM generalizes several important algorithmic problems such as perfect matching and restricted minimum weight spanning tree problems.
When introducing the problem in 1982, Papadimitriou and Yannakakis conjectured EM to be NP-complete. Later however, Mulmuley et al. presented a randomized polynomial time algorithm for EM, which puts EM in RP. Given that to decide whether or not RP=P represents a big open challenge in complexity theory, this makes it unlikely for EM to be NP-complete, and in fact indicates the possibility of a deterministic polynomial time algorithm. EM remains one of the few natural combinatorial problems in RP which are not known to be contained in P, making it an interesting instance for testing the hypothesis RP=P.
Despite EM being quite well-known, attempts to devise deterministic polynomial algorithms have remained illusive during the last 40 years and progress has been lacking even for very restrictive classes of input graphs. In this paper we push the frontier of positive results forward by proving that EM can be solved in deterministic polynomial time for input graphs of bounded independence number, and for bipartite input graphs of bounded bipartite independence number. This generalizes previous positive results for complete (bipartite) graphs which were the only known results for EM on dense graphs.
Cite as
Nicolas El Maalouly and Raphael Steiner. Exact Matching in Graphs of Bounded Independence Number. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{elmaalouly_et_al:LIPIcs.MFCS.2022.46,
author = {El Maalouly, Nicolas and Steiner, Raphael},
title = {{Exact Matching in Graphs of Bounded Independence Number}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {46:1--46:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.46},
URN = {urn:nbn:de:0030-drops-168447},
doi = {10.4230/LIPIcs.MFCS.2022.46},
annote = {Keywords: Perfect Matching, Exact Matching, Independence Number, Parameterized Complexity}
}
Document
CNF Encodings of Parity
Abstract
The minimum number of clauses in a CNF representation of the parity function x₁ ⊕ x₂ ⊕ … ⊕ x_n is 2^{n-1}. One can obtain a more compact CNF encoding by using non-deterministic variables (also known as guess or auxiliary variables). In this paper, we prove the following lower bounds, that almost match known upper bounds, on the number m of clauses and the maximum width k of clauses: 1) if there are at most s auxiliary variables, then m ≥ Ω(2^{n/(s+1)}/n) and k ≥ n/(s+1); 2) the minimum number of clauses is at least 3n. We derive the first two bounds from the Satisfiability Coding Lemma due to Paturi, Pudlák, and Zane using a tight connection between CNF encodings and depth-3 circuits. In particular, we show that lower bounds on the size of a CNF encoding of a Boolean function imply depth-3 circuit lower bounds for this function.
Cite as
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, and Nikita Slezkin. CNF Encodings of Parity. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{emdin_et_al:LIPIcs.MFCS.2022.47,
author = {Emdin, Gregory and Kulikov, Alexander S. and Mihajlin, Ivan and Slezkin, Nikita},
title = {{CNF Encodings of Parity}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {47:1--47:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.47},
URN = {urn:nbn:de:0030-drops-168455},
doi = {10.4230/LIPIcs.MFCS.2022.47},
annote = {Keywords: encoding, parity, lower bounds, circuits, CNF}
}
Document
On the Number of Quantifiers as a Complexity Measure
Abstract
In 1981, Neil Immerman described a two-player game, which he called the "separability game" [Neil Immerman, 1981], that captures the number of quantifiers needed to describe a property in first-order logic. Immerman’s paper laid the groundwork for studying the number of quantifiers needed to express properties in first-order logic, but the game seemed to be too complicated to study, and the arguments of the paper almost exclusively used quantifier rank as a lower bound on the total number of quantifiers. However, last year Fagin, Lenchner, Regan and Vyas [Fagin et al., 2021] rediscovered the game, provided some tools for analyzing them, and showed how to utilize them to characterize the number of quantifiers needed to express linear orders of different sizes. In this paper, we push forward in the study of number of quantifiers as a bona fide complexity measure by establishing several new results. First we carefully distinguish minimum number of quantifiers from the more usual descriptive complexity measures, minimum quantifier rank and minimum number of variables. Then, for each positive integer k, we give an explicit example of a property of finite structures (in particular, of finite graphs) that can be expressed with a sentence of quantifier rank k, but where the same property needs 2^Ω(k²) quantifiers to be expressed. We next give the precise number of quantifiers needed to distinguish two rooted trees of different depths. Finally, we give a new upper bound on the number of quantifiers needed to express s-t connectivity, improving the previous known bound by a constant factor.
Cite as
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, and Ryan Williams. On the Number of Quantifiers as a Complexity Measure. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fagin_et_al:LIPIcs.MFCS.2022.48,
author = {Fagin, Ronald and Lenchner, Jonathan and Vyas, Nikhil and Williams, Ryan},
title = {{On the Number of Quantifiers as a Complexity Measure}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {48:1--48:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.48},
URN = {urn:nbn:de:0030-drops-168460},
doi = {10.4230/LIPIcs.MFCS.2022.48},
annote = {Keywords: number of quantifiers, multi-structural games, complexity measure, s-t connectivity, trees, rooted trees}
}
Document
Non-Determinism in Lindenmayer Systems and Global Transformations
Abstract
Global transformations provide a categorical framework for capturing synchronous rewriting systems, generalizing cellular automata to dynamical systems over dynamic spaces. Originally developed for addressing deterministic dynamical systems, the presented work raises the question of non-determinism. While a usual approach is to develop a general non-deterministic setting where deterministic systems can be retrieved as a specific case, we show here that by choosing the right parametrization, global transformations can already be used to handle non-determinism. Context-free Lindenmayer systems, already shown to be captured by global transformation in the deterministic case, are used to illustrate the approach. From this concrete example, the formal obstructions are exhibited, leading to a solution involving a 2-categorical monad and its associated Kleisli construction.
Cite as
Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. Non-Determinism in Lindenmayer Systems and Global Transformations. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fernandez_et_al:LIPIcs.MFCS.2022.49,
author = {Fernandez, Alexandre and Maignan, Luidnel and Spicher, Antoine},
title = {{Non-Determinism in Lindenmayer Systems and Global Transformations}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {49:1--49:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.49},
URN = {urn:nbn:de:0030-drops-168470},
doi = {10.4230/LIPIcs.MFCS.2022.49},
annote = {Keywords: Global Transformations, Non-deterministic Dynamical Systems, Lindenmayer Systems, Category Theory}
}
Document
A Robust Class of Languages of 2-Nested Words
Abstract
Regular nested word languages (a.k.a. visibly pushdown languages) strictly extend regular word languages, while preserving their main closure and decidability properties. Previous works have shown that considering languages of 2-nested words, i.e. words enriched with two matchings (a.k.a. 2-visibly pushdown languages), is not as successful: the corresponding model of automata is not closed under determinization. In this work, inspired by homomorphic representations of indexed languages, we identify a subclass of 2-nested words, which we call 2-wave words. This class strictly extends the class of nested words, while preserving its main properties. More precisely, we prove closure under determinization of the corresponding automaton model, we provide a logical characterization of the recognized languages, and show that the corresponding graphs have bounded treewidth. As a consequence, we derive important closure and decidability properties. Last, we show that the word projections of the languages we define belong to the class of linear indexed languages.
Cite as
Séverine Fratani, Guillaume Maurras, and Pierre-Alain Reynier. A Robust Class of Languages of 2-Nested Words. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fratani_et_al:LIPIcs.MFCS.2022.50,
author = {Fratani, S\'{e}verine and Maurras, Guillaume and Reynier, Pierre-Alain},
title = {{A Robust Class of Languages of 2-Nested Words}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {50:1--50:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.50},
URN = {urn:nbn:de:0030-drops-168485},
doi = {10.4230/LIPIcs.MFCS.2022.50},
annote = {Keywords: Nested word, Determinization, Indexed languages}
}
Document
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Abstract
For a graph G, a subset S ⊆ V(G) is called a resolving set if for any two vertices u,v ∈ V(G), there exists a vertex w ∈ S such that d(w,u) ≠ d(w,v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [GT 61 in Garey and Johnson’s book]. In the realm of parameterized complexity, Hartung and Nichterlein [CCC 2013] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is FPT when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the feedback vertex set number. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the treewidth. Regarding the parameterization by the vertex cover number, we prove that Metric Dimension does not admit a polynomial kernel under this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the parameter is the distance to clique. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.
Cite as
Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{galby_et_al:LIPIcs.MFCS.2022.51,
author = {Galby, Esther and Khazaliya, Liana and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar},
title = {{Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {51:1--51:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.51},
URN = {urn:nbn:de:0030-drops-168496},
doi = {10.4230/LIPIcs.MFCS.2022.51},
annote = {Keywords: Metric Dimension, Parameterized Complexity, Feedback Vertex Set}
}
Document
Graph Similarity Based on Matrix Norms
Abstract
Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graph-based data. In this paper, we study the computational complexity of a family of similarity measures based on quantifying the mismatch between the two graphs, that is, the "symmetric difference" of the graphs under an optimal alignment of the vertices. An important example is similarity based on graph edit distance. While edit distance calculates the "global" mismatch, that is, the number of edges in the symmetric difference, our main focus is on "local" measures calculating the maximum mismatch per vertex.
Mathematically, our similarity measures are best expressed in terms of the adjacency matrices: the mismatch between graphs is expressed as the difference of their adjacency matrices (under an optimal alignment), and we measure it by applying some matrix norm. Roughly speaking, global measures like graph edit distance correspond to entrywise matrix norms like the Frobenius norm and local measures correspond to operator norms like the spectral norm.
We prove a number of strong NP-hardness and inapproximability results even for very restricted graph classes such as bounded-degree trees.
Cite as
Timo Gervens and Martin Grohe. Graph Similarity Based on Matrix Norms. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{gervens_et_al:LIPIcs.MFCS.2022.52,
author = {Gervens, Timo and Grohe, Martin},
title = {{Graph Similarity Based on Matrix Norms}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {52:1--52:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.52},
URN = {urn:nbn:de:0030-drops-168509},
doi = {10.4230/LIPIcs.MFCS.2022.52},
annote = {Keywords: graph similarity, approximate graph isomorphism, graph matching}
}
Document
Approximation Algorithms for Covering Vertices by Long Paths
Abstract
Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least k vertices is considered long. When k ≤ 3, the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4, the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O(1))-approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4. Both algorithms are based on local improvement, and their performance analyses are done via amortization.
Cite as
Mingyang Gong, Jing Fan, Guohui Lin, and Eiji Miyano. Approximation Algorithms for Covering Vertices by Long Paths. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{gong_et_al:LIPIcs.MFCS.2022.53,
author = {Gong, Mingyang and Fan, Jing and Lin, Guohui and Miyano, Eiji},
title = {{Approximation Algorithms for Covering Vertices by Long Paths}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {53:1--53:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.53},
URN = {urn:nbn:de:0030-drops-168517},
doi = {10.4230/LIPIcs.MFCS.2022.53},
annote = {Keywords: Path cover, k-path, local improvement, amortized analysis, approximation algorithm}
}
Document
The Hamilton Compression of Highly Symmetric Graphs
Abstract
We say that a Hamilton cycle C = (x₁,…,x_n) in a graph G is k-symmetric, if the mapping x_i ↦ x_{i+n/k} for all i = 1,…,n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x₁,…,x_n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i.e., all information about the graph is compressed into a 360^∘/k wedge of the drawing. We refer to the maximum k for which there exists a k-symmetric Hamilton cycle in G as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The cycles we construct have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.
Cite as
Petr Gregor, Arturo Merino, and Torsten Mütze. The Hamilton Compression of Highly Symmetric Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{gregor_et_al:LIPIcs.MFCS.2022.54,
author = {Gregor, Petr and Merino, Arturo and M\"{u}tze, Torsten},
title = {{The Hamilton Compression of Highly Symmetric Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {54:1--54:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.54},
URN = {urn:nbn:de:0030-drops-168529},
doi = {10.4230/LIPIcs.MFCS.2022.54},
annote = {Keywords: Hamilton cycle, Gray code, hypercube, permutahedron, Johnson graph, Cayley graph, abelian group, vertex-transitive}
}
Document
Dispersing Obnoxious Facilities on Graphs by Rounding Distances
Abstract
We continue the study of δ-dispersion, a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that every two facilities have distance at least δ from each other.
Our main technical contribution is an efficient procedure to "round-up" distance δ. It transforms a δ-dispersed set S into a δ^⋆-dispersed set S^⋆ of same size where distance δ^⋆ is a potentially slightly larger rational a/b with a numerator a upper bounded by the longest (not-induced) path in the input graph.
Based on this rounding procedure and connections to the distance-d independent set problem we derive a number of algorithmic results. When parameterized by treewidth, the problem is in XP. When parameterized by treedepth the problem is FPT and has a matching lower bound on its time complexity under ETH. Moreover, we can also settle the parameterized complexity with the solution size as parameter using our rounding technique: δ-Dispersion is FPT for every δ ≤ 2 and W[1]-hard for every δ > 2.
Further, we show that δ-dispersion is NP-complete for every fixed irrational distance δ, which was left open in a previous work.
Cite as
Tim A. Hartmann and Stefan Lendl. Dispersing Obnoxious Facilities on Graphs by Rounding Distances. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hartmann_et_al:LIPIcs.MFCS.2022.55,
author = {Hartmann, Tim A. and Lendl, Stefan},
title = {{Dispersing Obnoxious Facilities on Graphs by Rounding Distances}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {55:1--55:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.55},
URN = {urn:nbn:de:0030-drops-168536},
doi = {10.4230/LIPIcs.MFCS.2022.55},
annote = {Keywords: facility location, parameterized complexity, packing}
}
Document
On the Binary and Boolean Rank of Regular Matrices
Abstract
A 0,1 matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers k, there exists a square regular 0,1 matrix with binary rank k, such that the Boolean rank of its complement is k^Ω̃(log k). Equivalently, the ones in the matrix can be partitioned into k combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is k^Ω̃(log k). This settles, in a strong form, a question of Pullman (Linear Algebra Appl., 1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer., 1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, Göös, Jain, and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers k, there exists a regular graph with biclique partition number k and chromatic number k^Ω̃(log k).
Cite as
Ishay Haviv and Michal Parnas. On the Binary and Boolean Rank of Regular Matrices. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{haviv_et_al:LIPIcs.MFCS.2022.56,
author = {Haviv, Ishay and Parnas, Michal},
title = {{On the Binary and Boolean Rank of Regular Matrices}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {56:1--56:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.56},
URN = {urn:nbn:de:0030-drops-168545},
doi = {10.4230/LIPIcs.MFCS.2022.56},
annote = {Keywords: Binary rank, Boolean rank, Regular matrices, Non-deterministic communication complexity, Biclique partition number, Chromatic number}
}
Document
Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Abstract
Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that FewP ⊆ ⊕ P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappy"-ness) of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_PRIMES.
Cite as
Lane A. Hemaspaandra, Mandar Juvekar, Arian Nadjimzadah, and Patrick A. Phillips. Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hemaspaandra_et_al:LIPIcs.MFCS.2022.57,
author = {Hemaspaandra, Lane A. and Juvekar, Mandar and Nadjimzadah, Arian and Phillips, Patrick A.},
title = {{Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {57:1--57:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.57},
URN = {urn:nbn:de:0030-drops-168552},
doi = {10.4230/LIPIcs.MFCS.2022.57},
annote = {Keywords: structural complexity theory, computational complexity theory, ambiguity-limited NP, counting classes, P-printable sets}
}
Document
Independent Set Reconfiguration on Directed Graphs
Abstract
Directed Token Sliding asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. Directed Token Sliding is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions.
In this paper, we initiate the algorithmic study of Directed Token Sliding. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees [Demaine et al. TCS 2015], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which yield an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences.
Cite as
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, and Kunihiro Wasa. Independent Set Reconfiguration on Directed Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ito_et_al:LIPIcs.MFCS.2022.58,
author = {Ito, Takehiro and Iwamasa, Yuni and Kobayashi, Yasuaki and Nakahata, Yu and Otachi, Yota and Takahashi, Masahiro and Wasa, Kunihiro},
title = {{Independent Set Reconfiguration on Directed Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {58:1--58:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.58},
URN = {urn:nbn:de:0030-drops-168567},
doi = {10.4230/LIPIcs.MFCS.2022.58},
annote = {Keywords: Combinatorial reconfiguration, token sliding, directed graph, independent set, graph algorithm}
}
Document
Automating OBDD proofs is NP-hard
Abstract
We prove that the proof system OBDD(∧, weakening) is not automatable unless P = NP. The proof is based upon the celebrated result of [Albert Atserias and Moritz Müller, 2019] about the hardness of automatability for resolution. The heart of the proof is lifting with multi-output indexing gadget from resolution block-width to dag-like multiparty number-in-hand communication protocol size with o(n) parties, where n is the number of variables in the non-lifted formula. A similar lifting theorem for protocols with n+1 participants was proved by [Göös et al., 2020] to establish the hardness of automatability result for Cutting Planes.
Cite as
Dmitry Itsykson and Artur Riazanov. Automating OBDD proofs is NP-hard. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{itsykson_et_al:LIPIcs.MFCS.2022.59,
author = {Itsykson, Dmitry and Riazanov, Artur},
title = {{Automating OBDD proofs is NP-hard}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {59:1--59:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.59},
URN = {urn:nbn:de:0030-drops-168575},
doi = {10.4230/LIPIcs.MFCS.2022.59},
annote = {Keywords: proof complexity, OBDD, automatability, lifting, dag-like communication}
}
Document
Not All Strangers Are the Same: The Impact of Tolerance in Schelling Games
Abstract
Schelling’s famous model of segregation assumes agents of different types, who would like to be located in neighborhoods having at least a certain fraction of agents of the same type. We consider natural generalizations that allow for the possibility of agents being tolerant towards other agents, even if they are not of the same type. In particular, we consider an ordering of the types, and make the realistic assumption that the agents are in principle more tolerant towards agents of types that are closer to their own according to the ordering. Based on this, we study the strategic games induced when the agents aim to maximize their utility, for a variety of tolerance levels. We provide a collection of results about the existence of equilibria, and their quality in terms of social welfare.
Cite as
Panagiotis Kanellopoulos, Maria Kyropoulou, and Alexandros A. Voudouris. Not All Strangers Are the Same: The Impact of Tolerance in Schelling Games. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kanellopoulos_et_al:LIPIcs.MFCS.2022.60,
author = {Kanellopoulos, Panagiotis and Kyropoulou, Maria and Voudouris, Alexandros A.},
title = {{Not All Strangers Are the Same: The Impact of Tolerance in Schelling Games}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {60:1--60:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.60},
URN = {urn:nbn:de:0030-drops-168589},
doi = {10.4230/LIPIcs.MFCS.2022.60},
annote = {Keywords: Schelling games, Equilibria, Price of anarchy, Price of stability}
}
Document
On the Skolem Problem for Reversible Sequences
Abstract
Given an integer linear recurrence sequence ⟨X_n⟩, the Skolem Problem asks to determine whether there is a natural number n such that X_n = 0. Recent work by Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell proved that the Skolem Problem is decidable for a class of reversible sequences of order at most seven. Here we give an alternative proof of their result. Our novel approach employs a powerful result for Galois conjugates that lie on two concentric circles due to Dubickas and Smyth.
Cite as
George Kenison. On the Skolem Problem for Reversible Sequences. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kenison:LIPIcs.MFCS.2022.61,
author = {Kenison, George},
title = {{On the Skolem Problem for Reversible Sequences}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {61:1--61:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.61},
URN = {urn:nbn:de:0030-drops-168590},
doi = {10.4230/LIPIcs.MFCS.2022.61},
annote = {Keywords: The Skolem Problem, Linear Recurrences, Verification}
}
Document
The Complexity of Computing Optimum Labelings for Temporal Connectivity
Abstract
A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph G, what is the smallest number |λ| of time-labels that we need to add to the edges of G such that the resulting temporal graph (G,λ) is temporally connected? As it turns out, this basic problem, called Minimum Labeling (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem Min. Aged Labeling (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e., maximum label) of the obtained temporal graph (G,λ). Second we consider the problem Min. Steiner Labeling (MSL), where the aim is now to have a temporal path between any pair of "important" vertices which lie in a subset R ⊆ V, which we call the terminals. This relaxed problem resembles the problem Steiner Tree in static (i.e., non-temporal) graphs. However, due to the requirement of strictly increasing labels in a temporal path, Steiner Tree is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely Min. Aged Steiner Labeling (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number |R| of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL remains NP-hard, it is in FPT with respect to the number |R| of terminals. That is, adding the age restriction, makes the above problems strictly harder (unless P=NP or W[1]=FPT).
Cite as
Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The Complexity of Computing Optimum Labelings for Temporal Connectivity. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{klobas_et_al:LIPIcs.MFCS.2022.62,
author = {Klobas, Nina and Mertzios, George B. and Molter, Hendrik and Spirakis, Paul G.},
title = {{The Complexity of Computing Optimum Labelings for Temporal Connectivity}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {62:1--62:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.62},
URN = {urn:nbn:de:0030-drops-168603},
doi = {10.4230/LIPIcs.MFCS.2022.62},
annote = {Keywords: Temporal graph, graph labeling, foremost temporal path, temporal connectivity, Steiner Tree}
}
Document
Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
Abstract
Parity games have witnessed several new quasi-polynomial algorithms since the breakthrough result of Calude et al. (STOC 2017). The combinatorial object underlying these approaches is a universal tree, as identified by Czerwiński et al. (SODA 2019). By proving a quasi-polynomial lower bound on the size of a universal tree, they have highlighted a barrier that must be overcome by all existing approaches to attain polynomial running time. This is due to the existence of worst case instances which force these algorithms to explore a large portion of the tree.
As an attempt to overcome this barrier, we propose a strategy iteration framework which can be applied on any universal tree. It is at least as fast as its value iteration counterparts, while allowing one to take bigger leaps in the universal tree. Our main technical contribution is an efficient method for computing the least fixed point of 1-player games. This is achieved via a careful adaptation of shortest path algorithms to the setting of ordered trees. By plugging in the universal tree of Jurdziński and Lazić (LICS 2017), or the Strahler universal tree of Daviaud et al. (ICALP 2020), we obtain instantiations of the general framework that take time O(mn²log nlog d) and O(mn²log³ n log d) respectively per iteration.
Cite as
Zhuan Khye Koh and Georg Loho. Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{koh_et_al:LIPIcs.MFCS.2022.63,
author = {Koh, Zhuan Khye and Loho, Georg},
title = {{Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {63:1--63:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.63},
URN = {urn:nbn:de:0030-drops-168619},
doi = {10.4230/LIPIcs.MFCS.2022.63},
annote = {Keywords: parity games, strategy iteration, value iteration, progress measure, universal trees}
}
Document
Countdown μ-Calculus
Abstract
We introduce the countdown μ-calculus, an extension of the modal μ-calculus with ordinal approximations of fixpoint operators. In addition to properties definable in the classical calculus, it can express (un)boundedness properties such as the existence of arbitrarily long sequences of specific actions. The standard correspondence with parity games and automata extends to suitably defined countdown games and automata. However, unlike in the classical setting, the scalar fragment is provably weaker than the full vectorial calculus and corresponds to automata satisfying a simple syntactic condition. We establish some facts, in particular decidability of the model checking problem and strictness of the hierarchy induced by the maximal allowed nesting of our new operators.
Cite as
Jędrzej Kołodziejski and Bartek Klin. Countdown μ-Calculus. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kolodziejski_et_al:LIPIcs.MFCS.2022.64,
author = {Ko{\l}odziejski, J\k{e}drzej and Klin, Bartek},
title = {{Countdown \mu-Calculus}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {64:1--64:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.64},
URN = {urn:nbn:de:0030-drops-168624},
doi = {10.4230/LIPIcs.MFCS.2022.64},
annote = {Keywords: countdown \mu-calculus, games, automata}
}
Document
Rabbits Approximate, Cows Compute Exactly!
Abstract
Valiant, in his seminal paper in 1979, showed an efficient simulation of algebraic formulas by determinants, showing that VF, the class of polynomial families computable by polynomial-sized algebraic formulas, is contained in VDet, the class of polynomial families computable by polynomial-sized determinants. Whether this containment is strict has been a long-standing open problem. We show that algebraic formulas can in fact be efficiently simulated by the determinant of tetradiagonal matrices, transforming the open problem into a problem about determinant of general matrices versus determinant of tetradiagonal matrices with just three non-zero diagonals. This is also optimal in a sense that we cannot hope to get the same result for matrices with only two non-zero diagonals or even tridiagonal matrices, thanks to Allender and Wang (Computational Complexity'16) which showed that the determinant of tridiagonal matrices cannot even compute simple polynomials like x_1 x_2 + x_3 x_4 + ⋯ + x_15 x_16.
Our proof involves a structural refinement of the simulation of algebraic formulas by width-3 algebraic branching programs by Ben-Or and Cleve (SIAM Journal of Computing'92). The tetradiagonal matrices we obtain in our proof are also structurally very similar to the tridiagonal matrices of Bringmann, Ikenmeyer and Zuiddam (JACM'18) which showed that, if we allow approximations in the sense of geometric complexity theory, algebraic formulas can be efficiently simulated by the determinant of tridiagonal matrices of a very special form, namely the continuant polynomial. The continuant polynomial family is closely related to the Fibonacci sequence, which was used to model the breeding of rabbits. The determinants of our tetradiagonal matrices, in comparison, is closely related to Narayana’s cows sequences, which was originally used to model the breeding of cows. Our result shows that the need for approximation can be eliminated by using Narayana’s cows polynomials instead of continuant polynomials, or equivalently, shifting one of the outer diagonals of a tridiagonal matrix one place away from the center.
Conversely, we observe that the determinant (or, permanent) of band matrices can be computed by polynomial-sized algebraic formulas when the bandwidth is bounded by a constant, showing that the determinant (or, permanent) of bandwidth k matrices for all constants k ≥ 2 yield VF-complete polynomial families. In particular, this implies that the determinant of tetradiagonal matrices in general and Narayana’s cows polynomials in particular yield complete polynomial families for the class VF.
Cite as
Balagopal Komarath, Anurag Pandey, and Nitin Saurabh. Rabbits Approximate, Cows Compute Exactly!. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{komarath_et_al:LIPIcs.MFCS.2022.65,
author = {Komarath, Balagopal and Pandey, Anurag and Saurabh, Nitin},
title = {{Rabbits Approximate, Cows Compute Exactly!}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {65:1--65:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.65},
URN = {urn:nbn:de:0030-drops-168637},
doi = {10.4230/LIPIcs.MFCS.2022.65},
annote = {Keywords: Algebraic complexity theory, Algebraic complexity classes, Determinant versus permanent, Algebraic formulas, Algebraic branching programs, Band matrices, Tridiagonal matrices, Tetradiagonal matrices, Continuant, Narayana’s cow sequence, Padovan sequence}
}
Document
Finding 3-Swap-Optimal Independent Sets and Dominating Sets Is Hard
Abstract
For PLS-complete local search problems, there is presumably no polynomial-time algorithm which finds a locally optimal solution, even though determining whether a solution is locally optimal and replacing it by a better one if this is not the case can be done in polynomial time.
We study local search for Weighted Independent Set and Weighted Dominating Set with the 3-swap neighborhood. The 3-swap neighborhood of a vertex set S in G is the set of vertex sets which can be obtained from S by exchanging at most three vertices. We prove the following dichotomy: On the negative side, the problem of finding a 3-swap-optimal independent set or dominating set is PLS-complete. On the positive side, locally optimal independent sets or dominating sets can be found in polynomial time when allowing all 3-swaps except a) the swaps that remove two vertices from the current solution and add one vertex to the solution or b) the swaps that remove one vertex from the current solution and add two vertices to the solution.
Cite as
Christian Komusiewicz and Nils Morawietz. Finding 3-Swap-Optimal Independent Sets and Dominating Sets Is Hard. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{komusiewicz_et_al:LIPIcs.MFCS.2022.66,
author = {Komusiewicz, Christian and Morawietz, Nils},
title = {{Finding 3-Swap-Optimal Independent Sets and Dominating Sets Is Hard}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {66:1--66:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.66},
URN = {urn:nbn:de:0030-drops-168644},
doi = {10.4230/LIPIcs.MFCS.2022.66},
annote = {Keywords: Local Search, Graph problems, 3-swap neighborhood, PLS-completeness}
}
Document
SAT-Based Circuit Local Improvement
Abstract
Finding exact circuit size is notoriously hard. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in the blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of this behavior is that the search space is enormous: the number of circuits of size s is s^Θ(s), the number of Boolean functions on n variables is 2^(2ⁿ).
In this paper, we explore the following natural heuristic idea for decreasing the size of a given circuit: go through all its subcircuits of moderate size and check whether any of them can be improved by reducing to SAT. This may be viewed as a local search approach: we search for a smaller circuit in a ball around a given circuit. Through this approach, we prove new upper bounds on the circuit size of various symmetric functions. We also demonstrate that some upper bounds that were proved by hand decades ago, can nowadays be found automatically in a few seconds.
Cite as
Alexander S. Kulikov, Danila Pechenev, and Nikita Slezkin. SAT-Based Circuit Local Improvement. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{kulikov_et_al:LIPIcs.MFCS.2022.67,
author = {Kulikov, Alexander S. and Pechenev, Danila and Slezkin, Nikita},
title = {{SAT-Based Circuit Local Improvement}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {67:1--67:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.67},
URN = {urn:nbn:de:0030-drops-168659},
doi = {10.4230/LIPIcs.MFCS.2022.67},
annote = {Keywords: circuits, algorithms, complexity theory, SAT, SAT solvers, heuristics}
}
Document
Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs
Abstract
The well-known Cluster Vertex Deletion problem (cluster-vd) asks for a given graph G and an integer k whether it is possible to delete at most k vertices of G such that the resulting graph is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs H for which cluster-vd on H-free graphs is polynomially solvable and for which it is NP-complete.
Cite as
Hoang-Oanh Le and Van Bang Le. Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 68:1-68:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{le_et_al:LIPIcs.MFCS.2022.68,
author = {Le, Hoang-Oanh and Le, Van Bang},
title = {{Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {68:1--68:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.68},
URN = {urn:nbn:de:0030-drops-168663},
doi = {10.4230/LIPIcs.MFCS.2022.68},
annote = {Keywords: Cluster vertex deletion, Vertex cover, Computational complexity, Complexity dichotomy}
}
Document
Reducing the Vertex Cover Number via Edge Contractions
Abstract
The Contraction(vc) problem takes as input a graph G on n vertices and two integers k and d, and asks whether one can contract at most k edges to reduce the size of a minimum vertex cover of G by at least d. Recently, Lima et al. [MFCS 2020, JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, Contraction(vc) admits an XP algorithm running in time f(d) ⋅ n^O(d). They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results:
- Contraction(vc) is W[1]-hard parameterized by k + d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k + d) ⋅ n^o(k + d) for any function f. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative.
- It is NP-hard to decide whether an instance (G, k, d) of {Contraction(vc)} is a Yes-instance even when k = d, hence enhancing our understanding of the classical complexity of the problem.
- Contraction(vc) can be solved in time 2^O(d) ⋅ n^{k - d + O(1)}. This XP algorithm improves the one of Lima et al. [MFCS 2020], which uses Courcelle’s theorem as a subroutine and hence, the f(d)-factor in the running time is non-explicit and probably very large. On the other hand, this shows that when k = d, the problem is FPT parameterized by d (or by k).
Cite as
Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, and Prafullkumar Tale. Reducing the Vertex Cover Number via Edge Contractions. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lima_et_al:LIPIcs.MFCS.2022.69,
author = {Lima, Paloma T. and dos Santos, Vinicius F. and Sau, Ignasi and Souza, U\'{e}verton S. and Tale, Prafullkumar},
title = {{Reducing the Vertex Cover Number via Edge Contractions}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {69:1--69:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.69},
URN = {urn:nbn:de:0030-drops-168671},
doi = {10.4230/LIPIcs.MFCS.2022.69},
annote = {Keywords: Blocker problems, edge contraction, vertex cover, parameterized complexity}
}
Document
Generalized Bundled Fragments for First-Order Modal Logic
Abstract
When we bundle quantifiers and modalities together (as in ∃x□, ◇∀x etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting bundled fragments of FOML. It is well-known that finding decidable fragments of FOML is hard, but existing work shows that certain bundled fragments are decidable [Anantha Padmanabha et al., 2018], without any restriction on the arity of predicates, the number of variables, or the modal scope. In this paper, we explore generalized bundles such as ∀x∀y□, ∀x∃y◇ etc., and map the terrain with regard to decidability, presenting both decidability and undecidability results. In particular, we propose the loosely bundled fragment, which is decidable over increasing domains and encompasses all known decidable bundled fragments.
Cite as
Mo Liu, Anantha Padmanabha, R. Ramanujam, and Yanjing Wang. Generalized Bundled Fragments for First-Order Modal Logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{liu_et_al:LIPIcs.MFCS.2022.70,
author = {Liu, Mo and Padmanabha, Anantha and Ramanujam, R. and Wang, Yanjing},
title = {{Generalized Bundled Fragments for First-Order Modal Logic}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {70:1--70:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.70},
URN = {urn:nbn:de:0030-drops-168684},
doi = {10.4230/LIPIcs.MFCS.2022.70},
annote = {Keywords: bundled fragments, first-order modal logic, decidability, tableaux}
}
Document
Membership Problems in Finite Groups
Abstract
We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed n ≥ 3, where n is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks [Eugene M. Luks, 1991], which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar.
Cite as
Markus Lohrey, Andreas Rosowski, and Georg Zetzsche. Membership Problems in Finite Groups. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2022.71,
author = {Lohrey, Markus and Rosowski, Andreas and Zetzsche, Georg},
title = {{Membership Problems in Finite Groups}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {71:1--71:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.71},
URN = {urn:nbn:de:0030-drops-168694},
doi = {10.4230/LIPIcs.MFCS.2022.71},
annote = {Keywords: algorithms for finite groups, intersection non-emptiness problems, knapsack problems in groups}
}
Document
Streaming Word Problems
Abstract
We study deterministic and randomized streaming algorithms for word problems of finitely generated groups. For finitely generated linear groups, metabelian groups and free solvable groups we show the existence of randomized streaming algorithms with logarithmic space complexity for their word problems. We also show that the class of finitely generated groups with a logspace randomized streaming algorithm for the word problem is closed under several group theoretical constructions: finite extensions, direct products, free products and wreath products by free abelian groups. We contrast these results with several lower bound. An example of a finitely presented group, where the word problem has only a linear space randomized streaming algorithm, is Thompson’s group F.
Cite as
Markus Lohrey and Lukas Lück. Streaming Word Problems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2022.72,
author = {Lohrey, Markus and L\"{u}ck, Lukas},
title = {{Streaming Word Problems}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {72:1--72:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.72},
URN = {urn:nbn:de:0030-drops-168707},
doi = {10.4230/LIPIcs.MFCS.2022.72},
annote = {Keywords: word problems for groups, streaming algorithms}
}
Document
A Universal Skolem Set of Positive Lower Density
Abstract
The Skolem Problem asks to decide whether a given integer linear recurrence sequence (LRS) has a zero term. Decidability of this problem has been open for many decades, with little progress since the 1980s. Recently, a new approach was initiated via the notion of a Skolem set - a set of positive integers relative to which the Skolem Problem is decidable. More precisely, 𝒮 is a Skolem set for a class ℒ of integer LRS if there is an effective procedure that, given an LRS in ℒ, decides whether the sequence has a zero in 𝒮. A recent work exhibited a Skolem set for the class of all LRS that, while infinite, had density zero. In the present work we construct a Skolem set of positive lower density for the class of simple LRS .
Cite as
Florian Luca, Joël Ouaknine, and James Worrell. A Universal Skolem Set of Positive Lower Density. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 73:1-73:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{luca_et_al:LIPIcs.MFCS.2022.73,
author = {Luca, Florian and Ouaknine, Jo\"{e}l and Worrell, James},
title = {{A Universal Skolem Set of Positive Lower Density}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {73:1--73:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.73},
URN = {urn:nbn:de:0030-drops-168711},
doi = {10.4230/LIPIcs.MFCS.2022.73},
annote = {Keywords: Linear Recurrence Sequences, Skolem Problem, Exponential Diophantine Equations, Sieve Methods}
}
Document
Learning Deterministic Visibly Pushdown Automata Under Accessible Stack
Abstract
We study the problem of active learning deterministic visibly pushdown automata. We show that in the classical L^*-setting, efficient active learning algorithms are not possible. To overcome this difficulty, we propose the accessible stack setting, where the algorithm has the read and write access to the stack. In this setting, we show that active learning can be done in polynomial time in the size of the target automaton and the counterexamples provided by the teacher. As counterexamples of exponential size are inevitable, we consider an algorithm working with words in a compressed representation via (visibly) Straight-Line Programs. Employing compression allows us to obtain an algorithm where the teacher and the learner work in time polynomial in the size of the target automaton alone.
Cite as
Jakub Michaliszyn and Jan Otop. Learning Deterministic Visibly Pushdown Automata Under Accessible Stack. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 74:1-74:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{michaliszyn_et_al:LIPIcs.MFCS.2022.74,
author = {Michaliszyn, Jakub and Otop, Jan},
title = {{Learning Deterministic Visibly Pushdown Automata Under Accessible Stack}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {74:1--74:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.74},
URN = {urn:nbn:de:0030-drops-168729},
doi = {10.4230/LIPIcs.MFCS.2022.74},
annote = {Keywords: visibly pushdown automata, automata inference, minimization}
}
Document
Cohomology in Constraint Satisfaction and Structure Isomorphism
Abstract
Constraint satisfaction (CSP) and structure isomorphism (SI) are among the most well-studied computational problems in Computer Science. While neither problem is thought to be in PTIME, much work is done on PTIME approximations to both problems. Two such historically important approximations are the k-consistency algorithm for CSP and the k-Weisfeiler-Leman algorithm for SI, both of which are based on propagating local partial solutions. The limitations of these algorithms are well-known – k-consistency can solve precisely those CSPs of bounded width and k-Weisfeiler-Leman can only distinguish structures which differ on properties definable in C^k. In this paper, we introduce a novel sheaf-theoretic approach to CSP and SI and their approximations. We show that both problems can be viewed as deciding the existence of global sections of presheaves, ℋ_k(A,B) and ℐ_k(A,B) and that the success of the k-consistency and k-Weisfeiler-Leman algorithms correspond to the existence of certain efficiently computable subpresheaves of these. Furthermore, building on work of Abramsky and others in quantum foundations, we show how to use Čech cohomology in ℋ_k(A,B) and ℐ_k(A,B) to detect obstructions to the existence of the desired global sections and derive new efficient cohomological algorithms extending k-consistency and k-Weisfeiler-Leman. We show that cohomological k-consistency can solve systems of equations over all finite rings and that cohomological Weisfeiler-Leman can distinguish positive and negative instances of the Cai-Fürer-Immerman property over several important classes of structures.
Cite as
Adam Ó Conghaile. Cohomology in Constraint Satisfaction and Structure Isomorphism. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 75:1-75:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{oconghaile:LIPIcs.MFCS.2022.75,
author = {\'{O} Conghaile, Adam},
title = {{Cohomology in Constraint Satisfaction and Structure Isomorphism}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {75:1--75:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.75},
URN = {urn:nbn:de:0030-drops-168738},
doi = {10.4230/LIPIcs.MFCS.2022.75},
annote = {Keywords: constraint satisfaction problems, finite model theory, descriptive complexity, rank logic, Weisfeiler-Leman algorithm, cohomology}
}
Document
Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order
Abstract
We study constraint automata that accept data languages on finite string values. Each transition of the automaton is labelled with a constraint restricting the string value at the current and the next position of the data word in terms of the prefix and the suffix order. We prove that the emptiness problem for such constraint automata with Büchi acceptance condition is NL-complete. We remark that since the constraints are formed by two partial orders, prefix and suffix, we cannot exploit existing techniques for similar formalisms. Our decision procedure relies on a decidable characterization for those infinite paths in the graph underlying the automaton that can be completed with string values to yield a Büchi-accepting run. Our result is - to the best of our knowledge - the first work in this context that considers both prefix and suffix, and it is a first step into answering an open question posed by Demri and Deters.
Cite as
Dominik Peteler and Karin Quaas. Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{peteler_et_al:LIPIcs.MFCS.2022.76,
author = {Peteler, Dominik and Quaas, Karin},
title = {{Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {76:1--76:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.76},
URN = {urn:nbn:de:0030-drops-168743},
doi = {10.4230/LIPIcs.MFCS.2022.76},
annote = {Keywords: Data Languages, Strings, Constraints, Prefix, Suffix, Automata, Linear Temporal Logic}
}
Document
On Uniformization in the Full Binary Tree
Abstract
A function f uniformizes a relation R(X,Y) if R(X,f(X)) holds for every X in the domain of R. The uniformization problem for a logic L asks whether for every L-definable relation there is an L-definable function that uniformizes it. Gurevich and Shelah proved that no Monadic Second-Order (MSO) definable function uniformizes relation "Y is a one element subset of X" in the full binary tree. In other words, there is no MSO definable choice function in the full binary tree.
The cross-section of a relation R(X,Y) at D is the set of all E such that R(D,E) holds. Hence, a function that uniformizes R chooses one element from every non-empty cross-section. The relation "Y is a one element subset of X" has finite and countable cross-sections.
We prove that in the full binary tree the following theorems hold:
▶ Theorem (Finite cross-sections) If every cross-section of an MSO definable relation is finite, then it has an MSO definable uniformizer.
▶ Theorem (Uncountable cross-section) There is an MSO definable relation R such that every MSO definable relation included in R and with the same domain as R has an uncountable cross-section.
Cite as
Alexander Rabinovich. On Uniformization in the Full Binary Tree. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{rabinovich:LIPIcs.MFCS.2022.77,
author = {Rabinovich, Alexander},
title = {{On Uniformization in the Full Binary Tree}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {77:1--77:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.77},
URN = {urn:nbn:de:0030-drops-168757},
doi = {10.4230/LIPIcs.MFCS.2022.77},
annote = {Keywords: Monadic Second-Order Logic, Uniformization}
}
Document
An Exact Algorithm for Knot-Free Vertex Deletion
Abstract
The study of the Knot-Free Vertex Deletion problem emerges from its application in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph Q of a digraph D with at least two vertices is said to be a knot if there is no arc (u,v) of D with u ∈ V(Q) and v ∉ V(Q) (no-out neighbors of the vertices in Q). Given a directed graph D, the Knot-Free Vertex Deletion (KFVD) problem asks to compute a minimum-size subset S ⊂ V(D) such that D[V⧵S] contains no knots. There is no exact algorithm known for the KFVD problem in the literature that is faster than the trivial O^⋆(2ⁿ) brute-force algorithm. In this paper, we obtain the first non-trivial upper bound for KFVD by designing an exact algorithm running in time 𝒪^⋆(1.576ⁿ), where n is the size of the vertex set in D.
Cite as
M. S. Ramanujan, Abhishek Sahu, Saket Saurabh, and Shaily Verma. An Exact Algorithm for Knot-Free Vertex Deletion. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ramanujan_et_al:LIPIcs.MFCS.2022.78,
author = {Ramanujan, M. S. and Sahu, Abhishek and Saurabh, Saket and Verma, Shaily},
title = {{An Exact Algorithm for Knot-Free Vertex Deletion}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {78:1--78:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.78},
URN = {urn:nbn:de:0030-drops-168769},
doi = {10.4230/LIPIcs.MFCS.2022.78},
annote = {Keywords: exact algorithm, knot-free graphs, branching algorithm}
}
Document
On Extended Boundary Sequences of Morphic and Sturmian Words
Abstract
Generalizing the notion of the boundary sequence introduced by Chen and Wen, the nth term of the 𝓁-boundary sequence of an infinite word is the finite set of pairs (u,v) of prefixes and suffixes of length 𝓁 appearing in factors uyv of length n+𝓁 (n ≥ 𝓁 ≥ 1). Otherwise stated, for increasing values of n, one looks for all pairs of factors of length 𝓁 separated by n-𝓁 symbols.
For the large class of addable numeration systems U, we show that if an infinite word is U-automatic, then the same holds for its 𝓁-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). We also provide examples of numeration systems and U-automatic words with a boundary sequence that is not U-automatic. In the second part of the paper, we study the 𝓁-boundary sequence of a Sturmian word. We show that it is obtained through a sliding block code from the characteristic Sturmian word of the same slope. We also show that it is the image under a morphism of some other characteristic Sturmian word.
Cite as
Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. On Extended Boundary Sequences of Morphic and Sturmian Words. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 79:1-79:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{rigo_et_al:LIPIcs.MFCS.2022.79,
author = {Rigo, Michel and Stipulanti, Manon and Whiteland, Markus A.},
title = {{On Extended Boundary Sequences of Morphic and Sturmian Words}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {79:1--79:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.79},
URN = {urn:nbn:de:0030-drops-168776},
doi = {10.4230/LIPIcs.MFCS.2022.79},
annote = {Keywords: Boundary sequences, Sturmian words, Numeration systems, Automata, Graph of addition}
}
Document
Higher-Order Causal Theories Are Models of BV-Logic
Abstract
The Caus[-] construction takes a compact closed category of basic processes and yields a *-autonomous category of higher-order processes obeying certain signalling/causality constraints, as dictated by the type system in the resulting category. This paper looks at instances where the base category C satisfies additional properties yielding an affine-linear structure on Caus[𝒞] and a substantially richer internal logic. While the original construction only gave multiplicative linear logic, here we additionally obtain additives and a non-commutative, self-dual sequential product yielding a model of Guglielmi’s BV logic. Furthermore, we obtain a natural interpretation for the sequential product as "A can signal to B, but not vice-versa", which sits as expected between the non-signalling tensor and the fully-signalling (i.e. unconstrained) par. Fixing matrices of positive numbers for 𝒞 recovers the BV category structure of probabilistic coherence spaces identified by Blute, Panangaden, and Slavnov, restricted to normalised maps. On the other hand, fixing the category of completely positive maps gives an entirely new model of BV consisting of higher order quantum channels, encompassing recent work in the study of quantum and indefinite causal structures.
Cite as
Will Simmons and Aleks Kissinger. Higher-Order Causal Theories Are Models of BV-Logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{simmons_et_al:LIPIcs.MFCS.2022.80,
author = {Simmons, Will and Kissinger, Aleks},
title = {{Higher-Order Causal Theories Are Models of BV-Logic}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {80:1--80:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.80},
URN = {urn:nbn:de:0030-drops-168789},
doi = {10.4230/LIPIcs.MFCS.2022.80},
annote = {Keywords: Causality, linear logic, categorical logic, probabilistic coherence spaces, quantum channels}
}
Document
Space-Bounded Unitary Quantum Computation with Postselection
Abstract
Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343-1356] and Girish, Raz and Zhan [ICALP 2021, pp.73:1-73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz [TQC 2021, pp.10:1-10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.
Cite as
Seiichiro Tani. Space-Bounded Unitary Quantum Computation with Postselection. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{tani:LIPIcs.MFCS.2022.81,
author = {Tani, Seiichiro},
title = {{Space-Bounded Unitary Quantum Computation with Postselection}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {81:1--81:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.81},
URN = {urn:nbn:de:0030-drops-168798},
doi = {10.4230/LIPIcs.MFCS.2022.81},
annote = {Keywords: quantum complexity theory, space-bounded computation, postselection}
}
Document
Computing the Minimum Bottleneck Moving Spanning Tree
Abstract
Given a set P of n points that are moving in the plane, we consider the problem of computing a spanning tree for these moving points that does not change its combinatorial structure during the point movement. The objective is to minimize the bottleneck weight of the spanning tree (i.e., the largest Euclidean length of all edges) during the whole movement. The problem was solved in O(n²) time previously [Akitaya, Biniaz, Bose, De Carufel, Maheshwari, Silveira, and Smid, WADS 2021]. In this paper, we present a new algorithm of O(n^{4/3} log³ n) time.
Cite as
Haitao Wang and Yiming Zhao. Computing the Minimum Bottleneck Moving Spanning Tree. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{wang_et_al:LIPIcs.MFCS.2022.82,
author = {Wang, Haitao and Zhao, Yiming},
title = {{Computing the Minimum Bottleneck Moving Spanning Tree}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {82:1--82:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.82},
URN = {urn:nbn:de:0030-drops-168801},
doi = {10.4230/LIPIcs.MFCS.2022.82},
annote = {Keywords: minimum spanning tree, moving points, unit-disk range emptiness query, dynamic data structure}
}
Document
Improved Approximation Algorithms for the Traveling Tournament Problem
Abstract
The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizing the total distance traveled by all n teams (n is even). TTP-k is the problem with one more constraint that each team can have at most k consecutive home games or away games. The case where k = 3, TTP-3, is one of the most investigated cases. In this paper, we improve the approximation ratio of TTP-3 from (1.667+ε) to (1.598+ε), for any ε > 0. Previous schedules were constructed based on a Hamiltonian cycle of the graph. We propose a novel construction based on triangle packing. Then, by combining our triangle packing schedule with the Hamiltonian cycle schedule, we obtain the improved approximation ratio. The idea of our construction can also be extended to k ≥ 4. We demonstrate that the approximation ratio of TTP-4 can be improved from (1.750+ε) to (1.700+ε) by the same method. As an additional product, we also improve the approximation ratio of LDTTP-3 (TTP-3 where all teams are allocated on a straight line) from 4/3 to (6/5+ε).
Cite as
Jingyang Zhao, Mingyu Xiao, and Chao Xu. Improved Approximation Algorithms for the Traveling Tournament Problem. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{zhao_et_al:LIPIcs.MFCS.2022.83,
author = {Zhao, Jingyang and Xiao, Mingyu and Xu, Chao},
title = {{Improved Approximation Algorithms for the Traveling Tournament Problem}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {83:1--83:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.83},
URN = {urn:nbn:de:0030-drops-168813},
doi = {10.4230/LIPIcs.MFCS.2022.83},
annote = {Keywords: Sports scheduling, Traveling Tournament Problem, Approximation algorithm}
}