Today we can announce 3 new papers which were accepted to be presented at the ISAAC 2025 conference in Tainan, Taiwan on December 7-10th.
The first paper "A Parameterized Study of Secluded Structures in Directed Graphs" was written by Jonas Schmidt, Dr. Shaily Verma, Nadym Mallek.
The paper originates from Jonas’s master’s thesis, which he carried out with our chair last year. The work initiates the study of secluded subgraphs in directed graphs through the {In, Out, Total}-Secluded Π-Subgraph framework and analyzes its parameterized complexity for various properties Π. The paper presents new FPT algorithms, hardness results contrasting directed and undirected settings, and an improved FPT algorithm for Secluded Clique in undirected graphs.
The next paper "Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs" was written by Michelle Döring.
This paper studies the impact of rules imposed on networks that change over time (temporal graphs), such as whether the connections have a direction or whether it takes time to traverse a connection or not. We show that directed temporal graphs are fundamentally more powerful than undirected ones and settle several open questions about how these models relate. Our results also include ways to translate between different models, making it easier to apply known algorithms and insights across settings. This paper has won the "best student paper" award.
Finally, we have "Realization of Temporally Connected Graphs Based on Degree Sequences", written by Arnaud Casteigts, Michelle Döring and Nils Morawietz.
This paper revisits the classic “gossip problem,” where people call one another at scheduled times with the goal that eventually everyone has heard all information. While it is NP-hard to decide if this is possible when given a fixed graph (who talks to whom), we show that the problem becomes tractable only given how many calls each person can make and we can choose to whom. We give a complete set of rules that determine exactly when such gossip networks are possible, and provide fast constructive algorithms.
