Portal - MFCS 2022

MFCS 2022	August 22-26, 2022, Vienna, Austria
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) Stefan Szeider and Robert Ganian and Alexandra Silva (Eds.)
ISBN 978-3-95977-256-3, LIPICS Vol. 241	ISSN 1868-8969

Additional Information

License
Complete volume (PDF, 28 MB)
Search Publication Server

Authors

Bandopadhyay, Susobhan

Berendsohn, Benjamin Aram

Chakraborty, Supratik

Christiansen, Aleksander B. G.

dos Santos, Vinicius F.

Douéneau-Tabot, Gaëtan

Hemaspaandra, Lane A.

Kalyanasundaram, Subrahmanyam

Kanellopoulos, Panagiotis

Kołodziejski, Jędrzej

Komarath, Balagopal

Komusiewicz, Christian

Kowalski, Dariusz R.

Kozma, László

Kulikov, Alexander S.

Rabinovich, Alexander

Reynier, Pierre-Alain

Vassilevska Williams, Virginia

Voudouris, Alexandros A.

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Szeider, Stefan ; Ganian, Robert ; Silva, Alexandra

Abstract | Document (512 KB) | BibTeX

Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk)

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Sagunov, Danil ; Simonov, Kirill

Abstract | Document (588 KB) | BibTeX

Modern Dynamic Data Structures (Invited Talk)

Authors: Henzinger, Monika

Abstract | Document (510 KB) | BibTeX

An Updated Survey of Bidding Games on Graphs (Invited Talk)

Authors: Avni, Guy ; Henzinger, Thomas A.

Abstract | Document (610 KB) | BibTeX

Probabilistic Model Checking for Strategic Equilibria-Based Decision Making: Advances and Challenges (Invited Talk)

Authors: Kwiatkowska, Marta ; Norman, Gethin ; Parker, David ; Santos, Gabriel ; Yan, Rui

Abstract | Document (951 KB) | BibTeX

Online Bipartite Matching and Adwords (Invited Talk)

Authors: Vazirani, Vijay V.

Abstract | Document (684 KB) | BibTeX

Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets

Authors: Abhinav, Ankit ; Bandopadhyay, Susobhan ; Banik, Aritra ; Kobayashi, Yasuaki ; Nagano, Shunsuke ; Otachi, Yota ; Saurabh, Saket

Abstract | Document (901 KB) | BibTeX

Comonadic semantics for hybrid logic

Authors: Abramsky, Samson ; Marsden, Dan

Abstract | Document (712 KB) | BibTeX

The Complexity of Periodic Energy Minimisation

Authors: Adamson, Duncan ; Deligkas, Argyrios ; Gusev, Vladimir V. ; Potapov, Igor

Abstract | Document (2,235 KB) | BibTeX

Weighted Counting of Matchings in Unbounded-Treewidth Graph Families

Authors: Amarilli, Antoine ; Monet, Mikaël

Abstract | Document (806 KB) | BibTeX

On Upward-Planar L-Drawings of Graphs

Authors: Angelini, Patrizio ; Chaplick, Steven ; Cornelsen, Sabine ; Da Lozzo, Giordano

Abstract | Document (1,436 KB) | BibTeX

RAC Drawings of Graphs with Low Degree

Authors: Angelini, Patrizio ; Bekos, Michael A. ; Katheder, Julia ; Kaufmann, Michael ; Pfister, Maximilian

Abstract | Document (869 KB) | BibTeX

Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs

Authors: Auger, David ; Coucheney, Pierre ; Duhazé, Loric

Abstract | Document (1,193 KB) | BibTeX

Graph Realization of Distance Sets

Authors: Bar-Noy, Amotz ; Peleg, David ; Perry, Mor ; Rawitz, Dror

Abstract | Document (645 KB) | BibTeX

On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph

Authors: Bar-Noy, Amotz ; Böhnlein, Toni ; Peleg, David ; Rawitz, Dror

Abstract | Document (698 KB) | BibTeX

Towards a Model Theory of Ordered Logics: Expressivity and Interpolation

Authors: Bednarczyk, Bartosz ; Jaakkola, Reijo

Abstract | Document (846 KB) | BibTeX

Algebraic Representations of Unique Bipartite Perfect Matching

Authors: Beniamini, Gal

Abstract | Document (882 KB) | BibTeX

Fixed-Point Cycles and Approximate EFX Allocations

Authors: Berendsohn, Benjamin Aram ; Boyadzhiyska, Simona ; Kozma, László

Abstract | Document (837 KB) | BibTeX

Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits

Authors: Bhargav, C. S. ; Dutta, Sagnik ; Saxena, Nitin

Abstract | Document (718 KB) | BibTeX

Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs

Authors: Bhyravarapu, Sriram ; Kalyanasundaram, Subrahmanyam ; Mathew, Rogers

Abstract | Document (697 KB) | BibTeX

Skolem Meets Schanuel

Authors: Bilu, Yuri ; Luca, Florian ; Nieuwveld, Joris ; Ouaknine, Joël ; Purser, David ; Worrell, James

Abstract | Document (771 KB) | BibTeX

Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems

Authors: Boehmer, Niclas ; Heeger, Klaus ; Niedermeier, Rolf

Abstract | Document (780 KB) | BibTeX

Tree Exploration in Dual-Memory Model

Authors: Bojko, Dominik ; Gotfryd, Karol ; Kowalski, Dariusz R. ; Pająk, Dominik

Abstract | Document (873 KB) | BibTeX

On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares

Authors: Bonacina, Ilario ; Galesi, Nicola ; Lauria, Massimo

Abstract | Document (760 KB) | BibTeX

Complete ZX-Calculi for the Stabiliser Fragment in Odd Prime Dimensions

Authors: Booth, Robert I. ; Carette, Titouan

Abstract | Document (953 KB) | BibTeX

Extending Partial Representations of Circle Graphs in Near-Linear Time

Authors: Brückner, Guido ; Rutter, Ignaz ; Stumpf, Peter

Abstract | Document (1,089 KB) | BibTeX

Boundaries to Single-Agent Stability in Additively Separable Hedonic Games

Authors: Bullinger, Martin

Abstract | Document (668 KB) | BibTeX

Bounded Degree Nonnegative Counting CSP

Authors: Cai, Jin-Yi ; Szabo, Daniel P.

Abstract | Document (727 KB) | BibTeX

Continuous Rational Functions Are Deterministic Regular

Authors: Carton, Olivier ; Douéneau-Tabot, Gaëtan

Abstract | Document (806 KB) | BibTeX

On Kernels for d-Path Vertex Cover

Authors: Červený, Radovan ; Choudhary, Pratibha ; Suchý, Ondřej

Abstract | Document (937 KB) | BibTeX

On Synthesizing Computable Skolem Functions for First Order Logic

Authors: Chakraborty, Supratik ; Akshay, S.

Abstract | Document (810 KB) | BibTeX

Sample Compression Schemes for Balls in Graphs

Authors: Chalopin, Jérémie ; Chepoi, Victor ; Mc Inerney, Fionn ; Ratel, Sébastien ; Vaxès, Yann

Abstract | Document (910 KB) | BibTeX

On Algorithms Based on Finitely Many Homomorphism Counts

Authors: Chen, Yijia ; Flum, Jörg ; Liu, Mingjun ; Xun, Zhiyang

Abstract | Document (746 KB) | BibTeX

Higher-Order Quantified Boolean Satisfiability

Authors: Chistikov, Dmitry ; Haase, Christoph ; Hadizadeh, Zahra ; Mansutti, Alessio

Abstract | Document (990 KB) | BibTeX

On Dynamic α + 1 Arboricity Decomposition and Out-Orientation

Authors: Christiansen, Aleksander B. G. ; Holm, Jacob ; Rotenberg, Eva ; Thomassen, Carsten

Abstract | Document (953 KB) | BibTeX

LO_v-Calculus: A Graphical Language for Linear Optical Quantum Circuits

Authors: Clément, Alexandre ; Heurtel, Nicolas ; Mansfield, Shane ; Perdrix, Simon ; Valiron, Benoît

Abstract | Document (872 KB) | BibTeX

Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-Calculus

Authors: Clément, Alexandre ; Perdrix, Simon

Abstract | Document (863 KB) | BibTeX

A Complexity Approach to Tree Algebras: the Polynomial Case

Authors: Colcombet, Thomas ; Jaquard, Arthur

Abstract | Document (845 KB) | BibTeX

Enumeration Classes Defined by Circuits

Authors: Creignou, Nadia ; Durand, Arnaud ; Vollmer, Heribert

Abstract | Document (803 KB) | BibTeX

Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set

Authors: D'Costa, Julian ; Lefaucheux, Engel ; Neumann, Eike ; Ouaknine, Joël ; Worrell, James

Abstract | Document (704 KB) | BibTeX

The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems

Authors: D'Costa, Julian ; Karimov, Toghrul ; Majumdar, Rupak ; Ouaknine, Joël ; Salamati, Mahmoud ; Worrell, James

Abstract | Document (730 KB) | BibTeX

New Lower Bounds and Upper Bounds for Listing Avoidable Vertices

Authors: Deng, Mingyang ; Vassilevska Williams, Virginia ; Zhong, Ziqian

Abstract | Document (767 KB) | BibTeX

Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times

Authors: Dereniowski, Dariusz ; Wrosz, Izajasz

Abstract | Document (707 KB) | BibTeX

On the Identity Problem for Unitriangular Matrices of Dimension Four

Authors: Dong, Ruiwen

Abstract | Document (702 KB) | BibTeX

Regular Monoidal Languages

Authors: Earnshaw, Matthew ; Sobociński, Paweł

Abstract | Document (960 KB) | BibTeX

Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP

Authors: Ehrmanntraut, Anton ; Egidy, Fabian ; Glaßer, Christian

Abstract | Document (699 KB) | BibTeX

Exact Matching in Graphs of Bounded Independence Number

Authors: El Maalouly, Nicolas ; Steiner, Raphael

Abstract | Document (906 KB) | BibTeX

CNF Encodings of Parity

Authors: Emdin, Gregory ; Kulikov, Alexander S. ; Mihajlin, Ivan ; Slezkin, Nikita

Abstract | Document (739 KB) | BibTeX

On the Number of Quantifiers as a Complexity Measure

Authors: Fagin, Ronald ; Lenchner, Jonathan ; Vyas, Nikhil ; Williams, Ryan

Abstract | Document (794 KB) | BibTeX

Non-Determinism in Lindenmayer Systems and Global Transformations

Authors: Fernandez, Alexandre ; Maignan, Luidnel ; Spicher, Antoine

Abstract | Document (654 KB) | BibTeX

A Robust Class of Languages of 2-Nested Words

Authors: Fratani, Séverine ; Maurras, Guillaume ; Reynier, Pierre-Alain

Abstract | Document (716 KB) | BibTeX

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Authors: Galby, Esther ; Khazaliya, Liana ; Mc Inerney, Fionn ; Sharma, Roohani ; Tale, Prafullkumar

Abstract | Document (781 KB) | BibTeX

Graph Similarity Based on Matrix Norms

Authors: Gervens, Timo ; Grohe, Martin

Abstract | Document (786 KB) | BibTeX

Approximation Algorithms for Covering Vertices by Long Paths

Authors: Gong, Mingyang ; Fan, Jing ; Lin, Guohui ; Miyano, Eiji

Abstract | Document (766 KB) | BibTeX

The Hamilton Compression of Highly Symmetric Graphs

Authors: Gregor, Petr ; Merino, Arturo ; Mütze, Torsten

Abstract | Document (1,690 KB) | BibTeX

Dispersing Obnoxious Facilities on Graphs by Rounding Distances

Authors: Hartmann, Tim A. ; Lendl, Stefan

Abstract | Document (800 KB) | BibTeX

On the Binary and Boolean Rank of Regular Matrices

Authors: Haviv, Ishay ; Parnas, Michal

Abstract | Document (640 KB) | BibTeX

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting

Authors: Hemaspaandra, Lane A. ; Juvekar, Mandar ; Nadjimzadah, Arian ; Phillips, Patrick A.

Abstract | Document (780 KB) | BibTeX

Independent Set Reconfiguration on Directed Graphs

Authors: Ito, Takehiro ; Iwamasa, Yuni ; Kobayashi, Yasuaki ; Nakahata, Yu ; Otachi, Yota ; Takahashi, Masahiro ; Wasa, Kunihiro

Abstract | Document (797 KB) | BibTeX

Automating OBDD proofs is NP-hard

Authors: Itsykson, Dmitry ; Riazanov, Artur

Abstract | Document (839 KB) | BibTeX

Not All Strangers Are the Same: The Impact of Tolerance in Schelling Games

Authors: Kanellopoulos, Panagiotis ; Kyropoulou, Maria ; Voudouris, Alexandros A.

Abstract | Document (804 KB) | BibTeX

On the Skolem Problem for Reversible Sequences

Authors: Kenison, George

Abstract | Document (680 KB) | BibTeX

The Complexity of Computing Optimum Labelings for Temporal Connectivity

Authors: Klobas, Nina ; Mertzios, George B. ; Molter, Hendrik ; Spirakis, Paul G.

Abstract | Document (1,241 KB) | BibTeX

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees

Authors: Koh, Zhuan Khye ; Loho, Georg

Abstract | Document (787 KB) | BibTeX

Countdown μ-Calculus

Authors: Kołodziejski, Jędrzej ; Klin, Bartek

Abstract | Document (726 KB) | BibTeX

Rabbits Approximate, Cows Compute Exactly!

Authors: Komarath, Balagopal ; Pandey, Anurag ; Saurabh, Nitin

Abstract | Document (680 KB) | BibTeX

Finding 3-Swap-Optimal Independent Sets and Dominating Sets Is Hard

Authors: Komusiewicz, Christian ; Morawietz, Nils

Abstract | Document (734 KB) | BibTeX

SAT-Based Circuit Local Improvement

Authors: Kulikov, Alexander S. ; Pechenev, Danila ; Slezkin, Nikita

Abstract | Document (753 KB) | BibTeX

Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs

Authors: Le, Hoang-Oanh ; Le, Van Bang

Abstract | Document (659 KB) | BibTeX

Reducing the Vertex Cover Number via Edge Contractions

Authors: Lima, Paloma T. ; dos Santos, Vinicius F. ; Sau, Ignasi ; Souza, Uéverton S. ; Tale, Prafullkumar

Abstract | Document (899 KB) | BibTeX

Generalized Bundled Fragments for First-Order Modal Logic

Authors: Liu, Mo ; Padmanabha, Anantha ; Ramanujam, R. ; Wang, Yanjing

Abstract | Document (855 KB) | BibTeX

Membership Problems in Finite Groups

Authors: Lohrey, Markus ; Rosowski, Andreas ; Zetzsche, Georg

Abstract | Document (764 KB) | BibTeX

Streaming Word Problems

Authors: Lohrey, Markus ; Lück, Lukas

Abstract | Document (730 KB) | BibTeX

A Universal Skolem Set of Positive Lower Density

Authors: Luca, Florian ; Ouaknine, Joël ; Worrell, James

Abstract | Document (694 KB) | BibTeX

Learning Deterministic Visibly Pushdown Automata Under Accessible Stack

Authors: Michaliszyn, Jakub ; Otop, Jan

Abstract | Document (715 KB) | BibTeX

Cohomology in Constraint Satisfaction and Structure Isomorphism

Authors: Ó Conghaile, Adam

Abstract | Document (801 KB) | BibTeX

Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order

Authors: Peteler, Dominik ; Quaas, Karin

Abstract | Document (627 KB) | BibTeX

On Uniformization in the Full Binary Tree

Authors: Rabinovich, Alexander

Abstract | Document (778 KB) | BibTeX

An Exact Algorithm for Knot-Free Vertex Deletion

Authors: Ramanujan, M. S. ; Sahu, Abhishek ; Saurabh, Saket ; Verma, Shaily

Abstract | Document (825 KB) | BibTeX

On Extended Boundary Sequences of Morphic and Sturmian Words

Authors: Rigo, Michel ; Stipulanti, Manon ; Whiteland, Markus A.

Abstract | Document (911 KB) | BibTeX

Higher-Order Causal Theories Are Models of BV-Logic

Authors: Simmons, Will ; Kissinger, Aleks

Abstract | Document (817 KB) | BibTeX

Space-Bounded Unitary Quantum Computation with Postselection

Authors: Tani, Seiichiro

Abstract | Document (773 KB) | BibTeX

Computing the Minimum Bottleneck Moving Spanning Tree

Authors: Wang, Haitao ; Zhao, Yiming

Abstract | Document (794 KB) | BibTeX

Improved Approximation Algorithms for the Traveling Tournament Problem

Authors: Zhao, Jingyang ; Xiao, Mingyu ; Xu, Chao

Abstract | Document (766 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)