Search

We study the Length-Bounded Cut problem for special graph classes and from a parameterized complexity viewpoint. Here, we are given a graph G , two vertices s and t , and positive integers β and λ. The task is to find a set F of at most β edges such that each s - t -path of length at most λ in G contains some edge in F. Bazgan et al. [20] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph is a proper interval graph. We confirm this conjecture by providing a dynamic-programming-based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [15] for Length-Bounded Cut parameterized by pathwidth by showing W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms. [ABSTRACT FROM AUTHOR]

The localization game is a pursuit-evasion game analogous to Cops and Robbers, where the robber is invisible and the cops send distance probes in an attempt to identify the location of the robber. We present a novel graph parameter called the localization capture time, which measures how long the localization game lasts assuming optimal play. We conjecture that the localization capture time is linear in the order of the graph, and show that the conjecture holds for graph families such as trees and interval graphs. We study bounds on the localization capture time for trees and its monotone property on induced subgraphs of trees and more general graphs. We give upper bounds for the localization capture time on the incidence graphs of projective planes. We finish with new bounds on the localization number and localization capture time using treewidth. [ABSTRACT FROM AUTHOR]

Birmele [ J Graph Theory 2003] proved that every graph with circumference t has treewidth at most [ABSTRACT FROM AUTHOR]

Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms. [ABSTRACT FROM AUTHOR]

Abstract: We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound. [Copyright &y& Elsevier]