FPT in two and three dimensions I will discuss geometric problems in low dimensional settings from the perspective of parameterized complexity. More precisely, I will discuss the problems of computing shortest homologous cycles, small spheres and small surfaces in 2-dimemsional simplicial complexes and problems about selection of subsets of points in 3 dimensional space.
Dynamic Programming Cores for Minor Containment and Related Problems The dynamic programming core model is a formalism introduced recently for the specification of dynamic programming algorithms operating on treelike decompositions. In this work, we introduce an algorithmic metatheorem for edition problems to classes of graphs of bounded treewidth. We apply our approach in the study of edition to minor-closed classes of graphs. Given a graph \(H\), the \(H\)-minor containment problem consists of determining whether a given graph \(G\) contains a… Read More »Friday 11:30 – Farhad Vadiee
Hyperbolic grids and hyperbolic planar graphs Hyperbolic grids arise from regular tilings of the hyperbolic plane, but can also be studied from a pure graph-theoretical perspective. They are special planar graphs with exponential growth. Gromov hyperbolicity is a related and widely studied parameter of metric spaces and graphs. In this talk I will introduce these notions in a computer-scientist-friendly manner, talk about why we should care about these things, and point out some problems that we should explore.
Tree Automatic Classes of Finite Structures of Bounded Width In this work, we introduce the notion of tree-automatic width of a finite relational structure, and the notion of width of an advice tree automatic class of structures. We prove several closure and decidability properties for classes of finite relational structures of bounded width, and establish several connections between such classes and structural graph theory, in particular in what concerns classes of graphs of bounded treewidth, bounded clique-width, bounded twin-width, and… Read More »Thursday 16:30 – Mateus De Oliveira Oliveira
Finding k-Secluded Trees Faster We revisit the \(k\)-Secluded Tree problem. Given a vertex-weighted undirected graph \(G\), its objective is to find a maximum-weight induced subtree\(T\) whose open neighborhood has size at most \(k\). We present a fixed-parameter tractable algorithm that solves the problem in time \(2^{O(k \log k)}* n^{O(1)}\), improving on a double-exponential running time from earlier work by Golovach, Heggernes, Lima, and Montealegre. Starting from a single vertex, our algorithm grows a \(k\)-secluded tree by branching on vertices in… Read More »Thursday 16:00 – Jari de Kroon
Parameterized Complexities of Independent Set Reconfiguration In this talk, we settle the parameterized complexities of several variants of independent set reconfiguration, parameterized by the number of tokens (or: the size of the independent sets). In this problem, we are given an undirected graph and two independent sets, \(I_1\) and \(I_2\) and ask whether there is a reconfiguration sequence going from \ to \(I_2\). If there is no limit on the number of moves, the problem is XL-complete. If the maximum… Read More »Thursday 12:00 – Celine Swennenhuis
Exploring temporal graphs: introducing interval-membership-width. Traditionally, one way of coping with computational intractability is to restrict inputs to some class which displays algorithmically exploitable structure. For problems on graphs, there is a vast literature on how to do this. However, real-world networks often cannot be realistically modelled as graphs since they are not static. Indeed, many networks change over time and their edges may appear or disappear (for instance friendships may change in a social network). Such networks are called… Read More »Thursday 11:30 – Ben Bumpus
Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion In the \(F\)-minor-free deletion problem we aim to find a minimum vertex set in a given graph that intersects all minor models of graphs from the family \(F\). The Vertex planarization problem is a special case of \(F\)-minor-free deletion for the family \(F = {K_5, K_{3,3}}\). Whenever the family \(F\) contains at least one planar graph, then \(F\)-minor-free deletion is known to admit a constant-factor approximation algorithm and a polynomial… Read More »Thursday 10:30 – Michal Wlodarzcyk
Parameterized Algorithms for Gerrymandering on Graphs Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. In this talk, we will look at the problem of gerrymandering over a network structure, where the voters are embedded in a graph, and the task is to partition the vertex set into k pairwise disjoint connected sets (called districts) such that the target candidate wins more districts than any other candidate. The… Read More »Wednesday 12:00 – Pallavi Jain
Paths and Cycles of Large Rank in Frameworks We provide fixed-parameter tractable (FPT) algorithms for the following generalization of the fundamental Longest Path and Longest Cycle problems. Following Lovász, we call by a framework a pair \((G,M)\), where \(G\) is an undirected graph and \(M\) is a matroid whose elements are the vertices of \(G\). Then for a framework \((G,M)\) and integer \(k\), the Max Rank Path/Cycle problem asks whether there is a path/cycle in \(G\) whose vertices form a… Read More »Wednesday 11:30 – Giannos Stamoulis