ALGO2024

IPEC 2024

Scope

The International Symposium on Parameterized and Exact Computation (IPEC) is an annual conference covering all aspects of parameterized and exact algorithms and complexity. Its 19th edition will be part of ALGO 2024, which also hosts ESA 2024 and other specialized conferences and workshops.

Important Dates

  • Abstract submission: 26 June 2024 (AoE)
  • Paper submission: 30 June 2024 (AoE)
  • Notification: 05 August 2024
  • Conference: 04-06 September 2024
  • Camera-ready version: early October

Accepted papers

  • Jonas Lill, Kalina Petrova, and Simon Weber: Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
  • Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri, and Amer Mouawad: Parameterized Shortest Path Reconfiguration
  • Jakub Balabán, Robert Ganian, and Mathis Rocton: Twin-Width Meets Feedback Edges and Vertex Integrity
  • Peter Strulo, M. S. Ramanujan, Václav Blažej, and Sushmita Gupta: On Controlling Knockout Tournaments Without Perfect Information
  • Ishay Haviv and Dror Rabinovich: Kernelization for Orthogonality Dimension
  • Peter Strulo, Václav Blažej, M. S. Ramanujan, and Satyabrata Jana: On the Parameterized Complexity of Eulerian Strong Component Deletion
  • Marvin Künnemann and Mirza Redzic: Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
  • Foivos Fioravantes, Nikolaos Melissinos, and Theofilos Triommatis: Parameterised distance to local irregularity
  • Matthias Kaul, Matthias Mnich, and Hendrik Molter: Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
  • Tomohiro Koana, Nidhi Purohit, and Kirill Simonov: Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
  • Katrin Casel, Tobias Friedrich, Aikaterini Niklanovits, Kirill Simonov, and Ziena Zeif: Combining Crown Structures for Vulnerability Measures
  • Yuxi Liu and Mingyu Xiao: Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k
  • Carla Groenland, Jesper Nederlof, and Tomohiro Koana: A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a Rooted K_4-Minor
  • Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond: Kick the cliques
  • Paul Bastide and Carla Groenland: Quasi-linear distance query reconstruction for graphs of bounded treelength
  • Ilan Doron-Arad, Ariel Kulik and Fabrizio Grandoni: Unsplittable Flow on a Short Path
  • Matthias Bentert, Fedor V. Fomin, Fanny Hauser, and Saket Saurabh: The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
  • Jakob Greilhuber and Roohani Sharma: Component Order Connectivity admits no polynomial kernel parameterized by the feedback vertex set number
  • Anna Zych-Pawlewicz and Marek Żochowski: Dynamic Parameterized Feedback Problems in Tournaments
  • Henning Fernau and Kevin Mann: Roman Hitting Functions
  • Karthik C. S., Euiwoong Lee, and Pasin Manurangsi: On Equivalence of Parameterized Inapproximability of k-median, k-max-coverage, and 2-CSP
  • Guilherme de Castro Mendes Gomes, Emanuel Juliano, Gabriel Martins, and Vinicius F. dos Santos: Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
  • Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan, and Ruben F.A. Verhaegh: Preprocessing to Reduce the Search Space for Odd Cycle Transversal
  • Jaroslav Garvardt and Christian Komusiewicz: Modularity Clustering parameterized by Max Leaf Number
  • Satyabrata Jana, Lawqueen Kanesh, Madhumita Kundu, and Saket Saurabh: Subset Feedback Vertex Set in Tournaments as Fast as Without the Subset

Invited talks

The invited tutorial will be given by Szymon Toruńczyk (University of Warsaw, Poland).

Title: Structurally tractable graph classes
Abstract: Sparsity theory, initiated by Ossona de Mendez and Nesetril, identifies those classes of sparse graphs that are tractable in various ways – algorithmically, combinatorially, and logically – as exactly the nowhere dense classes. An ongoing effort aims at generalizing sparsity theory to classes of graphs that are not necessarily sparse. The notion of twin-width, developed by Bonnet, Thomasse and co-authors, is a step in that direction. A theory unifying the two is anticipated. It is conjectured that the relevant notion characterising dense graph classes that are tractable, generalising nowhere denseness and bounded twin-width, is the notion of a monadically dependent class, introduced by Shelah in model theory. In this tutorial, I will discuss the fundamental notions and results in this quickly developing area. This development combines tools from structural graph theory, logic, and algorithms.

Furthermore, IPEC will host an invited talk by one of the 2024 EATCS-IPEC Nerode Prize winners: Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos.

Title: (Meta) Kernelization
Paper published at: J. ACM 63(5): 44:1-44:69 (2016), announced at Foundations of Computer Science (FOCS) 2010.
Abstract: In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this work we give two meta-theorems on kernelzation. The first theorem says that all problems expressible in Counting Monadic Second Order Logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.

Submission Guidelines

The papers are submitted via EasyChair.

Each submission is required to be in the LIPIcs format. We welcome submissions of the full version of the paper, with title page containing only the title and abstract and the references placed at the very end of paper. However, the first 12 pages (excluding the title page) should be enough to assess the paper. In particular, PC members and potential subreviewers may treat these 12 pages as the short version (the rest being read at their discretion). PC members (outside the PC chairs) are allowed to author or coauthor submissions, but these submissions will not be eligible for the best student paper and the best paper. Besides this constraint, to be eligible for the best student paper, all the authors must be students at the time of the submission.

When submitting a paper, please indicate Conflict of Interest with PC members. A CoI is limited to the following categories:

  • Family member or close friend.
  • Ph.D. advisor or advisee (no time limit), or postdoc or undergraduate mentor or mentee within the past 5 years.
  • Same affiliation.
  • Involved in an alleged incident of harassment. (It is not required that the incident be reported.)
  • Reviewer owes author a favor (e.g., recently requested a reference letter).
  • Frequent or recent collaborator whom you believe cannot objectively review your work.

Double-blind reviewing

As in previous years, IPEC employs a lightweight double-blind reviewing process. Submissions should not reveal the identity of the authors in any way. In particular, authors’ names, affiliations, and email addresses should not appear at the beginning or in the body of the submission. Authors should ensure that any references to their own related work is in the third person (e.g., not “We build on our previous work …” but rather “We build on the work of …”). The purpose of the double-blind reviewing is to help PC members and external reviewers come to an initial judgement about the paper without bias, not to make it impossible for them to discover the authors if they were to try. Nothing should be done in the name of anonymity that weakens the submission or makes the job of reviewing the paper more difficult. In particular, important references should not be omitted or anonymized. In addition, authors should feel free to disseminate their ideas or draft versions of their paper as they normally would. For example, authors may post drafts of their papers on the web, submit them to arXiv, and give talks on their research ideas. In case there exist publicly available versions of the submission online, the authors might mention this in their submission (without providing references/links), and briefly explain the differences if any. Alternatively, they might communicate the details to the chairs, who will keep them confidential unless revealing them to the PC is needed for a fair judgement. Authors with further questions on double-blind reviewing are encouraged to contact the PC chairs.

PACE 2024

The Parameterized Algorithms and Computational Experiments Challenge (PACE) was conceived in Fall 2015 to deepen the relationship between parameterized algorithms and practice. Topics from multivariate algorithms, exact algorithms, fine-grained complexity, and related fields are in scope.

This year’s challenge is about the one-sided crossing minimization problem (OCM). This problem involves arranging the nodes of a bipartite graph on two layers (typically horizontal), with one of the layers fixed, aiming to minimize the number of edge crossings. OCM is one of the basic building block used for drawing hierarchical graphs. It is NP-hard, even for trees, but admits good heuristics, can be constant-factor approximated and solved in FPT time.

For more details on the timeline and past challenges, please visit the PACE website.

Committees

Program Committee

  • Édouard Bonnet (ENS Lyon, LIP, France) (co-chair)
  • Nick Brettell (Victoria University of Wellington, New Zealand)
  • David Eppstein (University of California, Irvine, USA)
  • Piotr Faliszewski (AGH University, Kraków, Poland)
  • Andreas Emil Feldmann (University of Sheffield, UK)
  • Jacob Focke (CISPA Helmholtz Center for Information Security, Saarbrucken, Germany)
  • Panos Giannopoulos (City, University of London, UK)
  • Petr Hliněný (Masaryk University, Brno, Czech Republic)
  • Lars Jaffke (University of Bergen, Norway)
  • Petteri Kaski (Aalto University, Finland)
  • Eunjung Kim (CNRS, France and KAIST, South Korea)
  • Tuukka Korhonen (University of Bergen, Norway)
  • Stephan Kreutzer (TU Berlin, Germany)
  • Paloma T. Lima (IT University of Copenhagen, Denmark)
  • Karolina Okrasa (Warsaw University of Technology, Poland)
  • Anthony Perez (LIFO, University of Orléans, France)
  • Paweł Rzążewski (Warsaw University of Technology and University of Warsaw, Poland) (co-chair)
  • Ignasi Sau (LIRMM, CNRS, Université de Montpellier, France)
  • Darren Strash (Hamilton College, Clinton, USA)
  • Ryan Williams (Massachusetts Institute of Technology, Cambridge, USA)

Steering Committee