ISAAC 2023 Program
December 3
17:00
Welcome Reception (Room SEN)

December 4
8:50 Opening Remarks (Room KACHO (AB))
9:00

Invited Talk (Room KACHO (AB))
Seok-Hee Hong: Faithful Graph Drawing

10:00
Coffee BreakSession 1A (Room KACHO (A))
10:30 Petr Gregor, Torsten Mütze and Namrata

Session 1B (Room KACHO (B))
Gang Liu and Haitao Wang

Pattern-avoiding binary trees - generation, counting, andbijections
Duncan Adamson, Pamela Fleischmann, Annika Huch,
Tore Koß, Florin Manea and Dirk Nowotka
k-Universality of Regular Languages

On the Line-Separable Unit-Disk Coverage and Related Problems

Alessio Conte, Roberto Grossi, Giulia Punzi and Takeaki Uno

Michaela Borzechowski, Patrick Schnider and Simon WeberA Compact DAG for Storing and Searching Maximal Common
12:00 Subsequences

Walter Didimo, Michael Kaufmann, Giuseppe Liotta,
Giacomo Ortali and Maurizio Patrignani
Rectilinear-Upward Planarity Testing of Digraphs

An FPT Algorithm for Splitting a Necklace Among Two Thieves

Lunch (Room SEN)

Session 2A (Room KACHO (A))
13:30 Anubhav Dhar, Soumita Hait and Sudeshna Kolay
Efficient Algorithms for Euclidean Steiner Minimal Tree on NearConvex Terminal Sets
Henk Alkema and Mark de Berg

15:00

Session 2B (Room KACHO (B))
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guspiel,Petr Hlineny, Filip Pokrývka and Marek Sokołowski
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Lars Jaffke, Paloma T. Lima and Roohani Sharma

Geometric TSP on Sets

Structural Parameterizations of b-Coloring

Jannis Blauth, Meike Neuwohner, Luise Puhlmann andJens Vygen
Improved guarantees for the a priori TSP

Hovhannes Harutyunyan, Kamran Koupayi and Denis PankratovTemporal Separators with Deadlines

Coffee BreakSession 3A (Room KACHO (A))
15:30 Cornelius Brand and Alexandra Lassota
Fast Convolutions for Near-Convex Sequences
Joachim Gudmundsson, Zijin Huang, André van Renssen andSampson Wong
Computing a Subtrajectory Cluster from c-packed Trajectories

17:00

Hugo Akitaya, Maike Buchin, Majid Mirzanezhad, Leonie Ryvkin
and Carola Wenk
Realizability of Free Spaces of Curves

Session 3B (Room KACHO (B))
Bart M. P. Jansen, Jari J. H. de Kroon and Michal Wlodarczyk
Single-Exponential FPT Algorithms for Enumerating Secluded
F-Free Subgraphs and Deleting to Scattered Graph Classes
Jungho Ahn, Jinha Kim and O-Joung Kwon
Unified almost linear kernels for generalized covering and packing
problems on nowhere dense classes
Nicolas El Maalouly, Raphael Steiner and Lasse Wulf
Exact Matching: Correct Parity and FPT Parameterized byIndependence Number

December 5
9:00

Invited Talk (Room KACHO (AB))
Edith Elkind: Group Fairness: From Multiwinner Voting to Participatory Budgeting

10:00
Coffee BreakSession 4A (Room KACHO (A))
10:30 Sampriti Roy and Yadu Vasudev

Session 4B (Room KACHO (B))
Fedor Fomin, Petr Golovach, Tuukka Korhonen andGiannos Stamoulis

Testing properties of distributions in the streaming model

Computing paths of large rank in planar frameworks
deterministically

Ben Jourdan, Peter Macgregor and He Sun

Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio
Montecchiani and Kirill SimonovIs the Algorithmic Kadison-Singer Problem Hard?

The st-Planar Edge Completion Problem is Fixed-Parameter
Tractable

Bodo Manthey and Jesse van Rhijn

Frank Kammer and Johannes Meintrup

Improved Smoothed Analysis of 2-Opt for the Euclidean TSPSuccinct Planar Encoding with Minor Operations

12:00

Lunch (Room SEN)

Session 5A (Room KACHO (A))
13:30 Tomer Cohen, Ariel Kulik and Hadas Shachnai

Session 5B (Room KACHO (B))
Shuichi Hirahara and Dana Moshkovitz

Improved Approximation for Two-dimensional Vector Multiple
Knapsack

Regularization of Low Error PCPs and an Application to MCSP

Mong-Jen KaoKazuyuki Amano

Improved Approximation Algorithm for Capacitated Facility
Location with Uniform Facility Cost

Depth-Three Circuits for Inner Product and Majority Functions

Matthias Englert, Nicolaos Matsakis and Pavel Vesely

Supartha Podder, Penghui Yao and Zekun YeApproximation Guarantees for Shortest Superstrings: Simpler and15:00 BetterOn the fine-grained query complexity of symmetric functionsCoffee BreakSession 6A (Room KACHO (A))
15:30 Mark de Berg, Andrés López Martínez, and Frits Spieksma
Finding Diverse Minimum s-t Cuts

On the Complexity of the Eigenvalue Deletion Problem

Shuai Shao and Stanislav ŽivnýHuairui Chu and Bingkai LinA strongly polynomial-time algorithm for weighted general factors
with three feasible degrees

FPT Approximation using Treewidth: Capacitated Vertex Cover,Target Set Selection and Vector Dominating Set

Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli andFanny PascualDavid Eppstein and Daniel Frishberg

Non-Clairvoyant Makespan Minimization Scheduling with
17:00 Predictions
19:00
Banquet (Room KACHO(AB))
21:00

Session 6B (Room KACHO (B))
Neeldhara Misra, Harshil Mittal, Saket Saurabh andDhara Thakkar

Rapid mixing for the hardcore Glauber dynamics and otherMarkov chains in bounded-treewidth graphs

December 6
9:00

Best Paper Session (Room KACHO (AB))[Best Paper] Carl Feghali, Felicia Lucke, Daniel Paulusma and Bernard Ries:
Matching Cuts in Graphs of High Girth and H-Free Graphs[Best Paper] Ragesh Jaiswal and Amit Kumar:
Clustering What Matters in Constrained Settings: Improved Outlier to Outlier-Free Reductions

10:30[Best Student Paper] Nicola Cotumaccio: Prefix Sorting DFAs: a Recursive Algorithm

Coffee BreakSession 7A (Room KACHO (A))
11:00 Diptarka Chakraborty and Sanjana Dey

Session 7B (Room KACHO (B))
Gabriel Bathie, Tomasz Kociumaka and Tatiana StarikovskayaMatrix Completion: Approximating the Minimum Diameter

Small-space algorithms for the online language distance problem
for palindromes and squares

Jingbang Chen, Meng He, Ian Munro, Richard Peng, Kaiyu Wu
and Daniel Zhang

Giulia Bernardini, Gabriele Fici, Pawel Gawrychowski andSolon Pissis

Distance Queries over Dynamic Interval Graphs

Substring Complexity in Sublinear Space

12:00

Lunch (Room SEN)

Session 8A (Room KACHO (A))
13:30 Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich
and Tobias Stamm

Session 8B (Room KACHO (B))
Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora andStéphane Vialette

New Support Size Bounds for Integer Programming, Applied toMakespan Minimization on Uniformly Related Machines

Recognizing unit multiple intervals is hard

Yann Disser and Nils Mosis

Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen,
Paweł Rzążewski, Alexander Wolff and Johannes Zink

A unified worst case for classical simplex and policy iteration pivot
rules

Coloring and Recognizing Mixed Interval Graphs

Yusuke Kobayashi, Ryoga Mahara and Tamas Schwarcz

Joydeep Mukherjee and Tamojit Saha

Reconfiguration of the Union of Arborescences

Connected Vertex Cover on AT-free Graphs15:00
Coffee BreakSession 9A (Room KACHO (A))
15:30 Yusuke Kobayashi and Takashi Noguchi

Session 9B (Room KACHO (B))
Mark de Berg, Leyla Biabani, Morteza Monemizadeh andLeonidas Theocharous

An Approximation Algorithm for Two-Edge-Connected Subgraph
Problem via Triangle-free Two-Edge-CoverClustering in Polygonal Domains

Ting-Yu Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh,
Shi-Chun Tsai and Mong-Jen Kao

Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane andKosuke Sugiyama

On Min-Max Graph Balancing with Strict Negative CorrelationConstraints

Shortest Beer Path Queries based on Graph Decomposition

Kei Kimura and Kazuhisa Makino

Joachim Gudmundsson and Yuan Sha

A Combinatorial Certifying Algorithm for Linear Programming
17:00 Problems with Gainfree Leontief Substitution Systems

Shortest Beer Path Queries in Digraphs with Bounded Treewidth