IWOCA 2026 Attendance Report

(English translation of the original article mostly done by Gemini 3.1 Pro.)

I attended the international conference IWOCA 2026 last week. Here is a quick overview of some of the talks I found interesting.

Ad

Our paper was presented by my coauthor Shunsuke Hamada (2nd-year master’s). We received the Best Student Paper award!

Minimum Clique Bicoloring
Shunsuke Hamada, Yuto Okada, Hirotaka Ono, Yota Otachi
📗Conference Version

A clique coloring is a (not necessarily proper) vertex coloring such that every maximal clique contains at least two colors. It is known that many graph classes around perfect graphs are clique 2-colorable. In this paper, we introduced the problem of minimizing the number of colors on one side within a clique 2-coloring, and gave algorithms and hardness across various classes and parameters.

Talks I Found Interesting

They are listed in the order they were presented.

Parameterized Algorithms for Computing MAD Trees
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, André Nichterlein, Camille Richer
📗Conference Version 📕arXiv Version

A spanning tree that achieves the Minimum Average Distance is called a MAD Tree. More formally, it is a spanning tree $T$ that minimizes $\sum_{u, v \in V} \mathrm{dist}_T (u, v) / \binom{n}{2}$. This is apparently a classic problem, and algorithms were given for various graph classes. This paper starts the study of its parameterized complexity, showing that it is in XP parameterized by treewidth, FPT by vertex integrity and modular-width, and NP-complete for split graphs.

Minimizing the Weighted Makespan with Restarts on a Single Machine
Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton, Rob van Stee, Corinna Wambsganz
📗Conference Version 📕arXiv Version

(I’m not confident of my understanding)

This is a single-machine scheduling problem with the following settings:

• There is 1 machine that can process 1 job at a time.
• Job $j$ arrives at time $r_j$.
• Job $j$ takes $p_j$ units of time to complete.
• Job $j$ has a weight $w_j$.
• All jobs must be completed.
• Letting $C_j$ be the completion time of job $j$, the goal is to minimize the weighted makespan $\max_j \{w_j C_j\}$.
• A job currently being processed can be interrupted and re-executed, but it must start again from the beginning and will take $p_j$ units of time.
  • This is called a restart, whereas under preemption, it could resume from where it was interrupted.

They considered the online version of this problem (where jobs arrive at time $r_j$) and did a competitive ratio analysis.

Removable Online Knapsack: Exploiting Recourse and Bounded Item Sizes
Dimitris Fotakis, Laurent Gourvès, Aris Pagourtzis, Panagiotis Patsilinakos
📗Conference Version

This is also about an online algorithm, specifically for the online knapsack problem. It appears that in the standard? online knapsack problem, we assume the value $=$ the weight for every item, so in the following settings:

• Items arrive sequentially.
• The $i$-th item has a weight of $w_i \in (0,1]$, and its value is also $w_i$.
• For each item, you must decide on the spot whether to put it into the bag (whose capacity is $1$) or not.
• Maximize the total sum of the values (weights) in the bag at the end.

However, with just this setup, the competitive ratio can become arbitrarily small in the following adversarial case:

• First, an item with weight $=$ value of $\varepsilon > 0$ is presented.
• If you put it in the bag $\to$ then, an item of weight $1$ is presented, and the process ends (competitive ratio $\varepsilon / 1 = \varepsilon$).
• If you do not put it in the bag $\to$ the process ends without presenting any more items (competitive ratio $0 / \varepsilon = 0$).

Therefore, additional settings are usually introduced, and [Iwama & Taketomi, ICALP 2002] seems to be a representative example: In this prior research, they considered a setting where items already placed in the bag could be discarded, establishing an optimal competitive ratio of $(\sqrt{5}+1)/2 \approx 1.618$.

In this paper, in addition to removal, they considered a version adding two elements:

• (bound awareness) An upper bound on the item weights is given as prior knowledge.
• (recourse) Items that were previously rejected can be resurrected up to $k$ times (I believe).

They did a competitive ratio analysis on this expanded version. Furthermore, using that online algorithm, they also provided an adaptive algorithm (where the upper bound of the weight isn’t given as prior knowledge, but it operates assuming an upper bound $\to$ if the assumption is wrong, it repeatedly updates to achieve a certain competitive ratio).

One Sequence to Rule them All: O(1)-Time Parallel Generation of Mixed-Radix Gray Codes
Lucia Moura, Prangya Parida, Brett Stevens, Aaron Williams
📗Conference Version

(I’m not confident of my understanding)

This is research on the problem of enumerating sequences with mixed radices in a standard Gray code manner. For example, $\{0, 1\} \times \{0, 1\} \times \{0, 1, 2\}$ can be enumerated as 000 $\to$ 001 $\to$ 002 $\to$ 012 $\to$ 012 $\to$ 010 $\to$ 011 $\to$ 111 $\to$ 112 $\to$ 110 $\to$ 100 $\to$ 101 $\to$ 102 (see the abstract).

Algorithms that start from 000… and enumerate in worst-case $O(1)$ time per step are known, and it seems this is even mentioned in Knuth’s The Art of Computer Programming.

Probably the contribution of this paper is to given an algorithm to compute the $k$-th sequence (and the additional $O(n)$ memory part required for execution) for a specific(?) Gray code, which, for example, makes it possible to generate and test them in $p$-parallel by enumerating $N / p$ items each.

Realizing Planar Linkages in Polygonal Domains
Thomas Depian, Carolina Haase, Martin Nöllenburg, André Schulz
📗Conference Version 📕arXiv Version

Given a planar graph $G$ and the length of each edge $\ell \colon E \to \mathbb{R}$, this is a type of problem where you must embed the vertex set $V$ into $\mathbb{R}^2$ such that it is planar and satisfies the edge-length constraints. This problem was shown to be $\exists \mathbb{R}$-complete in [ADDELS, SoCG 2016] (JoCG, 2025), even for the unit-length case (i.e., all edge lengths are $1$).

In this paper, they considered a version with an additional constraint: a polygon is additionally given, and the graph must be drawn inside it. The presentation mainly focused on hardness results:

• It is XP / W[1]-hard parameterized by $|G|$ (since we are allowed to make a highly complex polygon).
• Even if $G$ is a path, it becomes NP-hard when the positions of its start and end positions are specified.

(As always in a computational geometry talk) it was a fun presentation showing intuitive reduction diagrams¹. (in the paper, Fig. 3 – Fig. 6). Other results are also mentioned in the Abstract.

An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
Nacim Oijid, Clara Marcille
📗Conference Version 📕arXiv Version

A Monitoring Edge-Geodetic set (MEG-set) of a graph $G$ is a vertex set $M \subseteq V$ that satisfies this condition: for any edge $e$, there exists a pair of vertices $u, v \in M$ such that $\mathrm{dist}_G(u,v) \lt \mathrm{dist}_{G-e}(u,v)$. In other words, it is a set of vertices capable of detecting edge deletions via shortest path lengths.

This concept was introduced in [Foucaud, Narayanan & Sulochana, CALDAM 2023], and its NP-hardness, along with polynomial-time algorithms for several classes, are known. Interestingly, most existing polynomial-time algorithms (except for cycles) seem to be established by showing the following property on their respective classes:

• Property (meg-minimal): Let’s call a vertex contained in every MEG-set a mandatory vertex. Then, the set of all mandatory vertices is a MEG-set.

When this property holds, that set is obviously the unique minimum MEG-set. Since a characterization (which is decidable in polynomial time) of whether a vertex is a mandatory vertex has been provided (Theorem 4.1, [FMMSST, DAM (2025)]), showing this property implies that the problem can be solved in polynomial time.

While this property was previously known for subclasses of chordal graphs like strongly chordal graphs and split graphs, this paper generalizes the result by proving it for chordal graphs as well.

Algorithmic Meta-Theorems for Distributed Computing
Pierre Fraigniaud
(Invited Talk)

The talk was mainly about a (deterministic) model-checking algorithm that runs in $O_{\varphi, \mathcal{G}}(\log n)$ rounds ([BFFGGMRT, STOC 2026]) for:

• The CONGEST model
• A local FO formula (an FO-formula $\varphi$ that can be checked just by seeing distance-$\leq r$ neighbor (for some $r = f(\varphi)$) for each vertex (I think))
• A graph class $\mathcal{G}$ with bounded expansion

For example, $C_4$-freeness is a local FO formula because we only need to check if the distance-$\leq 2$ neighbor of each vertex contains $C_4$. However, even $C_4$-freeness is a difficult problem in distributed computing. There is a lower bound indicating that $\tilde\Omega(\sqrt{n})$ rounds are required by cleverly constructing a graph to simulate the communication complexity of a two-player Set Disjointness problem. It was very interesting to hear about this to me who is not familiar with the area at all. Looking at the construction of the lower bound, it felt like bounded expansion is working effectively.

According to [Nešetřil & Ossona de Mendez, Distrib. Comput. (2016)], low treedepth coloring can be done in $O_{\mathcal{G}}(\log n)$ rounds in the CONGEST model (with bounded expansion), and subgraph detection can apparently be decided using that. (Though I didn’t quite catch how large the gap is) Whether this could be generalized to all local FO formulas had remained an open question since then, and it seems to have been affirmatively resolved in the STOC paper.