The Discrete Math Seminar at Iowa State University is held on Wednesday at 3:20-4:10 pm in Carver 401 .
Some old talks are available on YouTube.
The seminar is organized by Ramón García, Owen Henderschedt and Bernard Lidický.
Aug 26 Casey Tompkins (11am)
Title:
Abstract:
Aug 26 Michal Dvořák
Title: Pathfinding in Self-Deleting Graphs
Abstract: We study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices.
In particular, we study \emph{self-deleting graphs}, introduced by Carmesin et al.~\cite{carmesin2023hamiltonian}, which consist of a graph $G=(V, E)$ and a function $f\colon V\rightarrow 2^E$, where $f(v)$ is the set of edges that will be deleted after visiting the vertex $v$.
In the \textsc{(Shortest) Self-Deleting Path} problem we are given a self-deleting graph and its vertices $s$ and $t$, and we are asked to find a path from $s$ to $t$ (of at most a given length), such that it does not traverse an edge in $f(v)$ after visiting $v$ for any vertex $v$.
We prove that \textsc{Self-Deleting Path} is \NP-hard even if the given graph is outerplanar, bipartite, has maximum degree $3$, bandwidth $2$ and satisfies $|f(v)|\leq 1$ for each vertex $v$.
We show that \textsc{Shortest Self Deleting Path} is \W{1}-complete parameterized by the length of the sought path and that it is \W{1}-complete parameterized by the vertex cover number, feedback vertex set number and treedepth.
In order to obtain algorithmic results, we parameterize the problem by $\mu=\max_v |f(v)|$ -- the maximum size of $f(v)$ and the length of the sought path. By a nontrivial application of the color coding technique, we obtain \FPT algorithm for the combination of $\mu$ and the length of the sought path. This result allows us to obtain several \FPT algorithms for parameterization by a combination of $\mu$ and a structural parameter, such as shrub-depth or modular-width. These algorithms are obtained by reducing to a particular extremal question about density of edges in graphs containing hamiltonian paths.
Next, we show that under standard complexity theoretical assumptions, there is no polynomial kernel for \textsc{Shortest Self-Deleting Path} parameterized by the combination of vertex cover number, and $\mu$ already on $2$-outerplanar graphs.
Sep 2 Welcome all
Title:
Abstract:
Sep 9
Title:
Abstract:
Sep 16
Title:
Abstract:
Sep 23
Title:
Abstract:
Sep 30 Alexander Clifton
Title:
Abstract:
Oct 7 Go see colloquium of Shira Zerbib on Oct 6
Title:
Abstract:
Oct 14
Title:
Abstract:
Oct 21 Ignacy Buczek
Title:
Abstract:
Oct 28
Title:
Abstract:
Nov 4
Title:
Abstract:
Nov 11
Title:
Abstract:
Nov 18
Title:
Abstract:
Dec 2
Title:
Abstract:
Dec 9
Title:
Abstract:
Sep 18-19 The 66th Midwest Graph Theory Conference (MIGHTY LXVI)
Oct 24-25 Sectional AMS (Duluth)
Jan 12-15 JMM (Chicago)
Mar 8-12 58th Southeastern International Conference on Combinatorics, Graph Theory & Computing (Boca)
Jun 14-18 CanaDAM 2027 (Kelowna BC)
Summer Graduate Research Workshop in Combinatorics (GRWC 2027) (TBA)
Aug 4-7 MAA Mathfest (New Orleans)