Laura Larios-Jones

Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose et al.

Parameterized complexity has always been concerned with practical computing: by confining combinatorial explosion to a secondary parameter $k$, one can uncover why and how many NP-hard problems are effectively tackled in practice. Today, however, the scale of data has changed: scientists study Big Data, which is so large that even quadratic dependence in the total input size $n$ is unaffordable. Therefore, what constitutes a practical algorithm has also changed. Classically, parameterized complexity is blind to the difference between defining fixed parameter tractability multiplicatively (i.e. $f(k) \cdot n^c$) or additively (i.e. $f(k) + n^c$). But what if the constant $c$ is one and we require true linearity, is this distinction still inconsequential? Here, we define and explore Truly Linear FPT (TLFPT) -- that is $O(n)+f(k)$ -- and show that it is a strict subset of Linear FPT (LFPT) -- that is $O(n) \cdot f(k)$ -- via diagonalization. Populating TLFPT requires careful consideration of linear-time algorithmics and data structures. We meet many inhabitants of TLFPT: SAT, Vertex Cover, Min-Max Matching, $(n-k)$-Coloring, Diverse Pair of Matchings, $k$-Path, and $H$-Coloring. Our parameterizations are equally varied. Beyond classical parameters like solution size, we leverage two parameters, treedepth and BFS-width, which are particularly well-suited to the TLFPT regime. We do so by developing techniques based on depth- and breadth-first search. For parameterized complexity to be of service to the scientific community, we need to contend with Big Data. For sufficiently large inputs, FPT beyond linear may not suffice. Thus, there is a practical and theoretical need for more ambitious goals. TLFPT is a first step forward.

Jessica Enright, Samuel D. Hand, Laura Larios-Jones et al.

Temporal graphs are graphs whose edges are labelled with times at which they are active. Their time-sensitivity provides a useful model of real networks, but renders many problems studied on temporal graphs more computationally complex than their static counterparts. To contend with this, there has been recent work devising parameters for which temporal problems become tractable. One such parameter is vertex-interval-membership (VIM) width. Broadly, this gives a bound on the number of vertices we need to keep track of at any given time to solve many problems. Our contributions are two-fold. Firstly, we introduce a new parameter, tree-interval-membership (TIM) width, that generalises both VIM width and several existing generalisations. Secondly, we provide meta-algorithms for both VIM and TIM width which can be used to prove fixed-parameter-tractability for large families of problems, bypassing the need to give involved dynamic programming arguments for every problem. In doing this, we provide a characterisation of problems in FPT with respect to both parameters. We apply these algorithms to temporal versions of Hamiltonian path, dominating set, matching, and edge deletion to limit maximum reachability.