49th International Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2024 in Cochem

February 19-23, 2024, Cochem, Germany

SOFSEM has a special focus on Foundations of Computer Science and AI, in particular
algorithms, AI-based methods, computational complexity, formal models. More information on the SOFSEM conference series can be found here.


  • Free online access to the proceedings will be provided from February 12 until March 13, 2024 as EPUB or PDF.
  • The final conference program can be seen here.
  • We will have closed the registration on February 8th, 2024, local time.
  • Let us make clear that the conference venue is the youth hostel, i.e., everything concerning the conference (apart from the excursions) will happen there.
  • There will be a second Special Issue with Acta Informatica for this SOFSEM.
  • The Best (Student) Paper Awards have been selected; congratulations go to:
    • Shared Best Paper Award: Tesshu Hanaka, Hironori Kiya, Michael Lampis, Hirotaka Ono and Kanae Yoshiwatari. Faster Winner Determination Algorithms for (Colored) Arc Kayles
    • Shared Best Paper Award: Jesper Nederlof and Krisztina Szilágyi. Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
    • Best Student Paper Award: Christoph Grüne, Tom Janssen and Janosch Fuchs. The Complexity of Online Graph Games
  • Also thanks to Springer for sponsoring the corresponding award money!
  • The registration also includes your reservation for the youth hostel. You can already plan if you like to have a single room (about 55 € per night, meals included), a double room (about 46 €) or a room with >= 3 persons (about 40 €). Unfortunately, single rooms are fully booked now. For those who start planning their trip: Talks will start on MON morning right after breakfast, end they will end shortly before lunch on FRI (which we still take in together). The social program will take place on WED afternoon and evening (visiting Reichsburg and conference dinner) and on THU afternoon (top secret ...). We are supposed to leave the youth hostel again after FRI lunch, as the next group will then occupy the whole hostel.
  • The server for new submissions is closed now. The list of accepted papers can be found below.
  • We decided to have one or two online sessions at SOFSEM; so even if you cannot attend in person, it should be possible to present your accepted paper. However, we do prefer the whole event to be organized as an on-site event. In particular, we will not transmit on-site presentations outside the conference (online).
  • We welcome submissions of original research in Foundations of Computer Science and AI, formatted using LNCS style: at most 14 pages (including references) plus a clearly marked appendix. Firm abstract deadline: August 28th, 2023; full papers should be submitted until September 1st, 2023. The reviewing is single-blind. The Easychair submission server is now only open for updates https://easychair.org/conferences/?conf=sofsem2024.
  • We will have a Special Issue with the renowned Journal of Computer and System Sciences (now confirmed).
  • All titles of the invited talks have been added below to the speakers.
  • SOFSEM 24 proceedings will be published in the ARCoSS subline of LNCS.
  • There will be a Best Paper and a Best Student Paper Award sponsored by Springer.
  • All invited speakers have confirmed their on-site participation, see below.
  • SOFSEM 24 dates have been fixed: the conference will run for 4.5 days, ending FRI, Feb. 23rd 2024, at noon.

Accepted Papers

  • Alessandro Aloisio, Michele Flammini and Cosimo Vinci. Generalized Distance Polymatrix Games
  • Virginia Ardevol Martınez, Steven Chaplick, Steven Kelk, Ruben Meuwese, Matus Mihalak and Georgios Stamoulis. Relaxed agreement forests
  • Mutsunori Banbara, Shin-Ichi Minato, Hirotaka Ono and Ryuhei Uehara. On the Computational Complexity of Generalized Common Shape Puzzles
  • Arash Beikmohammadi, William Evans and Seyed Ali Tabatabaee. Fractional Bamboo Trimming and Distributed Windows Scheduling
  • Sebastian Berndt, Matthias Mnich and Tobias Stamm. New support bounds and proximity bounds for integer linear programming
  • Sriram Bhyravarapu, Lawqueen Kanesh, Mohanapriya A, Nidhi Purohit, Sadagopan Narasimhan and Saket Saurabh. On the Parameterized Complexity of Minus Domination
  • Ivan Bliznets and Jesper Nederlof. Exact and Parameterized Algorithms for Choosability
  • Ivan Bliznets, Jesper Nederlof and Krisztina Szilagyi. Parameterized Algorithms for Covering by Arithmetic Progressions
  • Stefano Crespi Reghizzi, Antonio Restivo and Pierluigi San Pietro. Row-column combination of Dyck words
  • Annalisa De Bonis. Group Testing in Arbitrary Hypergraphs and Related Combinatorial Structures
  • Jorke de Vlas. On the parameterized complexity of the Perfect Phylogeny problem
  • Jona Dirks, Enna Gerhard, Mario Grobler, Amer E. Mouawad and Sebastian Siebertz. Data reduction for directed feedback vertex set on graphs without long induced cycles
  • William Evans, Kassian Koeck and Stephen Kobourov. Visualization of Bipartite Graphs in Limited Window Size
  • Jiří Fiala, Oksana Firman, Giuseppe Liotta, Alexander Wolff and Johannes Zink. Outerplanar and Forest Storyplans
  • Alexander Firbas, Alexander Dobler, Fabian Holzer, Jakob Schafellner, Manuel Sorge, Anaïs Villedieu and Monika Wißmann. Cluster Vertex Splitting and Company
  • Oksana Firman, Tim Hegemann, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff and Johannes Zink. Morphing Graph Drawings in the Presence of Point Obstacles
  • Pamela Fleischmann, Lukas Haschke, Tim Löck and Dirk Nowotka. Word-Representable Graphs from a Word’s Perspective
  • Laurent Gourves and Aris Pagourtzis. Removable Online Knapsack with Bounded Size Items
  • Christoph Grüne, Tom Janssen and Janosch Fuchs. The Complexity of Online Graph Games
  • Tesshu Hanaka, Hironori Kiya, Michael Lampis, Hirotaka Ono and Kanae Yoshiwatari. Faster Winner Determination Algorithms for (Colored) Arc Kayles
  • Stefan Hoffmann. Automata Classes Accepting Languages Whose Commutative Closure is Regular
  • Jan Janousek and Štěpán Plachý. Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching
  • Yoshito Kawasaki, Diptarama Hendrian, Ryo Yoshinaka and Ayumi Shinohara. Query Learning of Minimal Deterministic Symbolic Finite Automata Separating Regular Languages
  • Christian Laußmann, Jörg Rothe and Tessa Seeger. Apportionment with Thresholds: Strategic Campaigns Are Easy in the Top-Choice But Hard in the Second-Chance Mode
  • Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson and Guillaume Theyssier. Distributed Certification of Majority Dynamics
  • Caroline Mattes, Alexander Ushakov and Armin Weiß. Complexity of Spherical Equations in Finite Groups
  • S. Mahmoud Mousawi and Sandra Zilles. Positive Characteristic Sets for Relational Pattern Languages
  • Jesper Nederlof and Krisztina Szilagyi. Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
  • Andreea-Teodora Nász. The Weighted HOM-Problem over Fields
  • Kévin Perrot, Sylvain Sené and Léah Tapin. Combinatorics of block-parallel automata networks
  • M. Praveen, Philippe Schnoebelen, Julien Veron and Isa Vialard. On the piecewise complexity of words and periodic words
  • Arseny Shur and Mikhail Rubinchik. Distance Labeling for Families of Cycles
  • Rustem Takhanov. On the induced problem for fixed-template CSPs

Program Chairs

  • Henning Fernau, Univ. Trier
  • Serge Gaspers, UNSW Sydney, Australia
  • Ralf Klasing, CNRS, Univ. Bordeaux, France

Important Dates

  • August, 28th, 2023, AOE: abstract deadline (firm)
  • September 4th, 2023, AOE: full paper deadline (firm), but please submit some version of your full paper until September 1st, 2023, AOE.
  • mid-November, 2023: author notification

Invited Speakers

  • Edith Elkind, Univ. Oxford, UK: Fairness in Multiwinner Voting
  • Sevag Gharibian, Univ. Paderborn, Germany: Quantum algorithms and complexity theory: Does theory meet practice?
  • Rob van Glabbeek, Univ. Edinburgh, UK & Stanford Univ., USA & UNSW, AUS: Modeling Time Qualitatively in Process Algebra and Concurrency Theory
  • Markus L Schmid, HU Berlin, Germany: The Information Extraction Framework of Document Spanners - An Overview of Concepts, Results, and Recent Developments
  • Sandra Zilles, Univ. Regina, Canada: Machine Teaching - A Combinatorial Approach to Machine Learning from Small Amounts of Data

Program Committee

  • Petra Berenbrink, Univ. Hamburg, Germany
  • Maike Buchin, Ruhr-Univ. Bochum, Germany
  • Elisabet Burjons, York Univ., Canada
  • Maria Chudnovsky, Univ. Princeton, USA
  • Sanjana Dey, Nat. Univ. Singapore
  • Sigrid Ewert, Univ. Witwatersrand, South Africa
  • Paola Flocchini, Univ. Ottawa, Canada
  • Florent Foucaud, LIMOS - Univ. Clermont Auvergne, France
  • Robert Ganian, TU Wien, Austria
  • Luisa Gargano, Univ. Salerno, Italy
  • Leszek Gasieniec, Univ. Liverpool, UK
  • Mingyu Guo, Univ. Adelaide, Australia
  • Diptarama Hendrian, Tohoku Univ., Japan
  • Ling-Ju Hung, National Taipei Univ. of Business, Taiwan
  • Tomasz Jurdziński, Univ. Wroclaw, Poland
  • Philipp Kindermann, Univ. Trier, Germany
  • Dominik Köppl, Univ. Münster, Germany
  • Mikko Koivisto, Univ. Helsinki, Finland
  • Rastislav Kráľovič, Comenius Univ., Slovakia
  • Yaping Mao, Qinghai Normal Univ., China
  • Kitty Meeks, Univ. Glasgow, UK
  • Hirotaka Ono, Univ. Nagoya, Japan
  • Marina Papatriantafilou, Chalmers Univ. Techn., Sweden
  • Tomasz Radzik, King's College London, UK
  • Peter Rossmanith, RWTH Aachen Univ., Germany
  • Sasha Rubin, Univ. Sydney, Australia
  • Maria Serna, Univ. Politècnica de Catalunya, Spain
  • Hadas Shachnai, Technion, Israel
  • Ulrike Stege, Univ. Victoria, Canada
  • Frank Stephan, NUS, Singapore
  • Jan van Leeuwen, Utrecht Univ., The Netherlands
  • Jiri Wiedermann, Czech Acad. Sci., Czech Republic
  • Petra Wolf, Univ. Bergen, Norway

List of Topics

  • algorithmic game theory
  • algorithmic learning theory
  • approximation algorithms
  • automata theory
  • coding theory
  • combinatorics, including polyhedral combinatorics
  • complexity theory
  • computational biology
  • computational geometry
  • computational models and computability
  • computational statistics
  • data compression: algorithms and theory
  • database theory
  • discrete structures
  • distributed algorithms
  • formal languages
  • formal methods
  • foundations of artificial intelligence
  • foundations of machine learning
  • games: algorithmic and complexity aspects
  • grammatical inference
  • graph algorithms, including applications like graph drawing
  • graph theory
  • information retrieval
  • information theory
  • kernelization algorithms
  • logic in computer science
  • network science
  • neural networks theory
  • online algorithms
  • quantum algorithms and computing
  • parallel computing
  • parameterized algorithms
  • probabilistic methods
  • randomized algorithms
  • reconfiguration and reoptimization
  • self-organizing systems
  • string algorithms


Explanation for eligibility of student paper:

To be eligible for the best student paper award, at least one of the paper authors must be a full-time (PhD) student at the time of submission, and the student(s) must have made a significant contribution to the paper.

Explanation of submissions of original papers

First of all, this means that the contents of a submitted paper must not have been published elsewhere, with a peer review process involved.  Hence, do not send your paper to a journal prior to the notification of authors of the conference. Simultaneous submission to other conferences or workshops with published proceedings is also disallowed. Then, there is no doubt about the originality of the paper’s content. There is no need to wait with sending the long version of a paper to a journal until the paper has been presented at the conference, although it is recommended waiting for this event, as sometimes authors receive additional feedback from the audience that is helpful for preparing the journal submission. This is why in Theoretical Computer Science, the current workflow seems to be to first put a technical report version of a paper on ArXive, then submit a short version to some conference, which might also lead to some updates of the ArXive version, and finally submit the full paper to a journal. Also, mind the possibility of being selected for the Special Issue (SI). The selected papers (invited to the SI) will only be announced after the conference.