16th Scandinavian Symposium and Workshops on Algorithm Theory SWAT 2018, June 18–20, 2018, Malmö University, Malmö, Sweden Edited by David Eppstein LIPIcs – Vol. 101 – SWAT 2018 www.dagstuhl.de/lipics Editors David Eppstein Computer Science Department University of California, Irvine Irvine, California, USA [email protected] ACM Classification 2012 Theory of computation → Design and analysis of algorithms ISBN 978-3-95977-068-2 Published online and open access by Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany. Online available at http://www.dagstuhl.de/dagpub/978-3-95977-068-2. Publication date June, 2018 Bibliographic information published by the Deutsche Nationalbibliothek The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available in the Internet at http://dnb.d-nb.de. License This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC-BY 3.0): http://creativecommons.org/licenses/by/3.0/legalcode. In brief, this license authorizes each and everybody to share (to copy, distribute and transmit) the work under the following conditions, without impairing or restricting the authors’ moral rights: Attribution: The work must be attributed to its authors. The copyright is retained by the corresponding authors. Digital Object Identifier: 10.4230/LIPIcs.SWAT.2018.0 ISBN 978-3-95977-068-2 ISSN 1868-8969 http://www.dagstuhl.de/lipics 0:iii LIPIcs – Leibniz International Proceedings in Informatics LIPIcs is a series of high-quality conference proceedings across all fields in informatics. LIPIcs volumes are published according to the principle of Open Access, i.e., they are available online and free of charge. Editorial Board Luca Aceto (Chair, Gran Sasso Science Institute and Reykjavik University) Susanne Albers (TU München) Chris Hankin (Imperial College London) Deepak Kapur (University of New Mexico) Michael Mitzenmacher (Harvard University) Madhavan Mukund (Chennai Mathematical Institute) Anca Muscholl (University Bordeaux) Catuscia Palamidessi (INRIA) Raimund Seidel (Saarland University and Schloss Dagstuhl – Leibniz-Zentrum für Informatik) Thomas Schwentick (TU Dortmund) Reinhard Wilhelm (Saarland University) ISSN 1868-8969 http://www.dagstuhl.de/lipics SWAT 2018 Contents Preface David Eppstein .................................................................. 0:ix Invited Talks Sampling-Based Motion Planning: From Intelligent CAD to Crowd Simulation to Protein Folding Nancy M. Amato ................................................................ 1:1–1:1 Optimizing Society? Ensuring Fairness in Automated Decision-Making Sorelle Friedler .................................................................. 2:1–2:1 Robustness Meets Algorithms Ankur Moitra .................................................................... 3:1–3:1 Regular Papers Economical Delone Sets for Approximating Convex Bodies Ahmed Abdelkader and David M. Mount ......................................... 4:1–4:12 Computing Shortest Paths in the Plane with Removable Obstacles Pankaj K. Agarwal, Neeraj Kumar, Stavros Sintos, and Subhash Suri ............ 5:1–5:15 On Romeo and Juliet Problems: Minimizing Distance-to-Sight Hee-Kap Ahn, Eunjin Oh, Lena Schlipf, Fabian Stehn, and Darren Strash ........ 6:1–6:13 Multistage Matchings Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos ... 7:1–7:13 Convex Hulls in Polygonal Domains Luis Barba, Michael Hoffmann, Matias Korman, and Alexander Pilz ............. 8:1–8:13 Tree Containment With Soft Polytomies Matthias Bentert, Josef Malík, and Mathias Weller .............................. 9:1–9:14 On the Size of Outer-String Representations Therese Biedl, Ahmad Biniaz, and Martin Derka ................................. 10:1–10:14 Flip Distance to some Plane Configurations Ahmad Biniaz, Anil Maheshwari, and Michiel Smid .............................. 11:1–11:14 Boundary Labeling for Rectangular Diagrams Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi, and Debajyoti Mondal . 12:1–12:14 Gathering by Repulsion Prosenjit Bose and Thomas C. Shermer ......................................... 13:1–13:12 Improved Bounds for Guarding Plane Graphs with Edges Ahmad Biniaz, Prosenjit Bose, Aurélien Ooms, and Sander Verdonschot ......... 14:1–14:12 Sparse Weight Tolerant Subgraph for Single Source Shortest Path Diptarka Chakraborty and Debarati Das .......................................... 15:1–15:15 16thScandinavianSymposiumandWorkshopsonAlgorithmTheory(SWAT2018). Editor: DavidEppstein LeibnizInternationalProceedingsinInformatics SchlossDagstuhl–Leibniz-ZentrumfürInformatik,DagstuhlPublishing,Germany 0:vi Contents An Improved Algorithm for Incremental DFS Tree in Undirected Graphs Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, and Tianyi Zhang ........ 16:1–16:12 Succinct Dynamic One-Dimensional Point Reporting Hicham El-Zein, J. Ian Munro, and Yakov Nekrich .............................. 17:1–17:11 Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices Khaled Elbassioni and Kazuhisa Makino ......................................... 18:1–18:14 The Parameterized Hardness of the k-Center Problem in Transportation Networks Andreas Emil Feldmann and Dániel Marx ........................................ 19:1–19:13 Algorithms for the Discrete Fréchet Distance Under Translation Omrit Filtser and Matthew J. Katz .............................................. 20:1–20:14 Partial Complementation of Graphs Fedor V. Fomin, Petr A. Golovach, Torstein J.F. Strømme, and Dimitrios M. Thilikos ........................................................... 21:1–21:13 New Algorithms for Distributed Sliding Windows Sutanu Gayen and N. V. Vinodchandran ......................................... 22:1–22:15 Parameterized Aspects of Strong Subgraph Closure Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Paloma T. Lima, and Charis Papadopoulos ...................................... 23:1–23:13 Parameterized Orientable Deletion Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora ................................................................... 24:1–24:13 SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms Lingxiao Huang, Yifei Jin, and Jian Li .......................................... 25:1–25:13 Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts Shang-En Huang and Seth Pettie ................................................ 26:1–26:12 Reconfiguration of Colorable Sets in Classes of Perfect Graphs Takehiro Ito and Yota Otachi .................................................... 27:1–27:13 Tight Lower Bounds for List Edge Coloring Łukasz Kowalik and Arkadiusz Socała ............................................ 28:1–28:12 Load Thresholds for Cuckoo Hashing with Double Hashing Michael Mitzenmacher, Konstantinos Panagiotou, and Stefan Walzer ............ 29:1–29:9 A Greedy Algorithm for Subspace Approximation Problem Nguyen Kim Thang .............................................................. 30:1–30:7 Planar 3-SAT with a Clause/Variable Cycle Alexander Pilz ................................................................... 31:1–31:13 Tree-Residue Vertex-Breaking: a new tool for proving hardness Erik D. Demaine and Mikhail Rudoy ............................................ 32:1–32:14 Contents 0:vii Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu ................................................. 33:1–33:12 SWAT 2018 Preface The Scandinavian Symposium and Workshops on Algorithm Theory (SWAT, formerly the Scandinavian Workshop on Algorithm Theory) has been offered every two years beginning in 1988, when it was offered in Halmstaf, Sweden. It alternates with its sister conference, the Algorithms and Data Structures Symposium (WADS), usually held in Canada. This year marks the 16th SWAT, and the fourth time the conference has been in Sweden. 92regularpapersweresubmittedtotheconference;fourwerewithdrawn,andtheprogram committee selected 30 of the remaining 88 papers for presentation at the conference. In addition, the conference program includes three invited talks, whose abstracts are included in the proceedings. The SWAT conference series is run by a steering committee consisting of Lars Arge (Aarhus University), Magnús M. Halldórsson (Reykjavík University), Andrzej Lingas (Lund University),JanArneTelle(UniversityofBergen),andEskoUkkonen(UniversityofHelsinki). This year’s conference is organized by Jesper Larsson and Bengt J. Nilsson (both of Malmö University). The program committee consisted of Mikkel Abrahamsen (University of Copenhagen), JoanBoyar(UniversityofSouthernDenmark),JingsenChen(LuleåUniversityofTechnology), DevdattDubhashi(ChalmersUniversityofTechnology),DavidEppstein(chair; Universityof California, Irvine), Zachary Friggstad (University of Alberta), Travis Gagie (Diego Portales University), Serge Gaspers (University of New South Wales), Iyad Kanj (DePaul University), Viggo Kann (KTH Royal Institute of Technology), Tsvi Kopelowitz (University of Waterloo), Christian Knauer (University of Bayreuth), Irina Kostitsyna (Eindhoven University of Technology), Shi Li (University at Buffalo), Daniel Lokshtanov (University of Bergen), MatthiasMnich(MaastrichtUniversityandRheinischeFriedrich-Wilhelms-UniversitätBonn), Sang-il Oum (Korea Advanced Institute of Science and Technology), Daniel Paulusma (DurhamUniversity),MarcinPilipczuk(UniversityofWarsaw),BenjaminRaichel(University of Texas at Dallas), Marcel Roeloffzen (National Institute of Informatics), Barna Saha (University of Massachusetts Amherst), Jukka Suomela (Aalto University), and Haitao Wang (Utah State University). 16thScandinavianSymposiumandWorkshopsonAlgorithmTheory(SWAT2018). Editor: DavidEppstein LeibnizInternationalProceedingsinInformatics SchlossDagstuhl–Leibniz-ZentrumfürInformatik,DagstuhlPublishing,Germany