10 papers
Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics
Florian Bridoux, Maximilien Gadouleau, David C. Kutner +1
The central object in this work is the Boolean network, a function . Often identified with is its dynamics , the digraph with exactly $\{x \to y…
: Truly Linear FPT
Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose +7
Parameterized complexity has always been concerned with practical computing: by confining combinatorial explosion to a secondary parameter , one can uncover why and how many NP-…
Steiner Forest for -Subgraph-Free Graphs
Tala Eagling-Vose, David C. Kutner, Felicia Lucke +4
Our main result is a full classification, for every connected graph , of the computational complexity of Steiner Forest on -subgraph-free graphs. To obtain this dichotomy, we…
Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
David C. Kutner, Anouk Sommer
In train networks, carefully-chosen delays may be beneficial for certain passengers, who would otherwise miss some connection. Given a simple (directed or undirected) temporal grap…
Generalising the maximum independent set algorithm via Boolean networks
Maximilien Gadouleau, David C. Kutner
A simple greedy algorithm to find a maximal independent set (MIS) in a graph starts with the empty set and visits every vertex, adding it to the set if and only if none of its neig…
Payment Scheduling in the Interval Debt Model
Tom Friedetzky, David C. Kutner, George B. Mertzios +2
The network-based study of financial systems has received considerable attention in recent years but has seldom explicitly incorporated the dynamic aspects of such systems. We cons…
Reconfigurable routing in data center networks
David C. Kutner, Iain A. Stewart
A hybrid network is a static (electronic) network that is augmented with optical switches. The Reconfigurable Routing Problem (RRP) in hybrid networks is the problem of finding set…
Words fixing the kernel network and maximum independent sets in graphs
Maximilien Gadouleau, David C. Kutner
The simple greedy algorithm to find a maximal independent set of a graph can be viewed as a sequential update of a Boolean network, where the update function at each vertex is the…
Temporal Reachability Dominating Sets: contagion in temporal graphs
David C. Kutner, Laura Larios-Jones
Given a population with dynamic pairwise connections, we ask if the entire population could be (indirectly) infected by a small group of initially infected individuals. We form…
Vibration-based communication for deafblind people
David C. Kutner, Sunčica Hadžidedić
Deafblind people have both hearing and visual impairments, which makes communication with other people often dependent on expensive technologies e.g., Braille displays, or on careg…