Search

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.

A connected path decomposition of a simple graph G is a path decomposition (X 1 , ... , X l) such that the subgraph of G induced by X 1 ∪ ⋯ ∪ X i is connected for each i ∈ { 1 , ... , l }. The connected pathwidth of G is then the minimum width over all connected path decompositions of G. We prove that for each fixed k , the connected pathwidth of any input graph can be computed in polynomial-time. This answers an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game. [ABSTRACT FROM AUTHOR]

In this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1, ... , pw(G) + 1}, there exists an interval supergraph G′ of G such that for its clique number it holds ω (G ′) ≤ (1 + 2 t) (pw (G) + 1) and the number of its edges is bounded by |E(G′)| ≤ (t + 2)p(G). In other words, the pathwidth and the profile of a graph can be simultaneously minimized within the factors of 1 + 2 t (plus a small constant) and t + 2, respectively. Note that for a fixed t, both upper bounds provide constant factor approximations. On the negative side, we show an example that proves that, for some graphs, there is no solution in which both parameters are optimal. In case of finding a chordal supergraph, the two corresponding graph parameters that reflect its clique size and number of edges are the treewidth and fill-in. We obtain that the treewidth and the fill-in problems are also 'orthogonal' in the sense that for some graphs, a solution that minimizes one of those parameters cannot minimize the other. As a motivating example, we recall graph searching games which illustrates a need of simultaneous minimization of these pairs of graph parameters. [ABSTRACT FROM AUTHOR]

In this paper, we provide results for the search number of the Cartesian product of graphs. We consider graphs on opposing ends of the spectrum: paths and cliques. Our main result determines the pathwidth of the product of cliques and provides a lower bound for the search number of the product of cliques. A consequence of this result is a bound for the search number of the product of arbitrary graphs G and H based on their respective clique numbers. [ABSTRACT FROM AUTHOR]

This paper tackles the well known graph searching problem, where a team of searchers aims at capturing an intruder in a network, modeled as a graph. This problem has been mainly studied for its relationship with the pathwidth of graphs. All variants of this problem assume that any node can be simultaneously occupied by several searchers. This assumption may be unrealistic, e.g., in the case of searchers modeling physical searchers, or may require each individual node to provide additional resources, e.g., in the case of searchers modeling software agents. We thus introduce and investigate exclusive graph searching, in which no two or more searchers can occupy the same node at the same time. As for the classical variants of graph searching, we study the minimum number of searchers required to capture the intruder. This number is called the exclusive search number of the considered graph. Exclusive graph searching appears to be considerably more complex than classical graph searching, for at least two reasons: (1) it does not satisfy the monotonicity property, and (2) it is not closed under minor. Moreover, we observe that the exclusive search number of a tree may differ exponentially from the values of classical search numbers (e.g., pathwidth). Nevertheless, we design a polynomial-time algorithm which, given any n-node tree T, computes the exclusive search number of T in time $$O(n^3)$$ . Moreover, for any integer k, we provide a characterization of the trees T with exclusive search number at most k. Finally, we prove that the ratio between the exclusive search number and the pathwidth of a graph is bounded by its maximum degree. [ABSTRACT FROM AUTHOR]

In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. In this paper, we study the complexity of the Exclusive Graph Searching variant. We show that the problem is NP-hard in planar graphs and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. [ABSTRACT FROM AUTHOR]

We consider a bicriterion generalization of the pathwidth problem: given integers k , l and a graph G , does there exist a path decomposition of G of width at most k and length (i.e., number of bags) at most l ? We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to k , the generalized problem is NP-complete for any fixed k ≥ 4 , and also for any fixed l ≥ 2 . On the other hand, we give a polynomial-time algorithm that constructs a minimum-length path decomposition of width at most k ≤ 3 for any disconnected input graph. As a by-product, we obtain an almost complete classification for connected graphs: the problem is NP-complete for any fixed k ≥ 5 , and polynomial for any k ≤ 3 . [ABSTRACT FROM AUTHOR]

Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q ≥ 0 , the q -limited search number, s q ( G ) , of a graph G is the smallest number of searchers required to capture an invisible fugitive in G , when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s 0 ( G ) corresponds to the pathwidth of a graph G , and s ∞ ( G ) to its treewidth. Determining s q ( G ) is NP-complete for any fixed q ≥ 0 in general graphs and s 0 ( T ) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q > 0 . We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rs q and is shown to be equal to the non-deterministic graph searching parameter s q for q = 0 , 1 , and at most twice s q for any q ≥ 2 (for any graph G ). Our main result is a polynomial time algorithm that computes rs q ( T ) for any tree T and any q ≥ 0 . This provides a 2-approximation of s q ( T ) for any tree T , and shows that the decision problem associated to s 1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest. [ABSTRACT FROM AUTHOR]

We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the monotonic zero-visibility copnumber can be bounded both above and below by positive multiples of the pathwidth. [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: The problems of (classical) searching and connected searching of weighted trees are known to be computationally hard. In this work we give a polynomial-time 3-approximation algorithm that finds a connected search strategy of a given weighted tree. This in particular yields constant factor approximation algorithms for the (non-connected) classical searching problems and for the weighted pathwidth problem for this class of graphs. [Copyright &y& Elsevier]

It is proven that the connected pathwidth of any graph G is at most 2 · pw(G)+1, where pw(G) is the pathwidth of G. The method is constructive, i.e., it yields an efficient algorithm that for a given path decomposition of width k computes a connected path decomposition of width at most 2k+1. The running time of the algorithm is O(dk²), where d is the number of "bags" in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality cs(G) ≤ 2s(G) + 3, where cs(G) and s(G) are the connected search number and the search number of G, respectively. Moreover, the algorithm presented in this work can be used to convert a given search strategy using k searchers into a (monotone) connected one using 2k + 3 searchers and starting at an arbitrary homebase. [ABSTRACT FROM AUTHOR]

We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis et al. (Inf. Comput. 113(1):50-79, ). It can be executed in an asynchronous environment, requires an overall computation time of O( nlog n), and n messages of log n+4 bits each. The main contribution of this work lies in the data structure proposed to design our algorithm, called hierarchical decomposition. This simple and flexible data structure is used for four operations: updating the node search number after addition or deletion of any tree-edges in a distributed fashion; computing it in a tree whose edges are added sequentially and in any order; computing other graph invariants such as the process number and the edge search number, by changing only initialization rules; extending our algorithms for trees and forests of unknown size (using messages of up to 2log n+5 bits). [ABSTRACT FROM AUTHOR]

We define helicopter cops and robber games with multiple robbers, extending previous research, which considered only the pursuit of a single robber. Our model is defined for robbers that are visible (their position in the graph is known to the cops) and active (they can move at any point in the game) but is easily adapted to other variants of the single-robber game that have been considered in the literature. We show that the game with many robbers is nonmonotone: that is, fewer cops are needed if the robbers are allowed to reoccupy positions that were previously unavailable to them. As the moves of the cops depend on the position of the visible robbers, strategies for such games should be interactive, but the game becomes, in a sense, less interactive as the initial number of robbers increases. We prove that the main parameter emerging from the game, which we denote mvams(G, r), captures a hierarchy of parameters between proper pathwidth and proper treewidth, and we completely characterize it for trees, extending analogous existing characterizations of the pathwidth of trees. Moreover, we prove an upper bound for mvams(G, r) on general graphs and show that this bound is reached by an infinite class of graphs. On the other hand, if we consider the robbers to be invisible and lazy, the resulting parameters collapse in all cases to either proper pathwidth or proper treewidth, giving a further case where the classical equivalence between visible, active robbers and invisible, lazy robbers does not hold. [ABSTRACT FROM AUTHOR]

Abstract: Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is . Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any , there exists a graph with connected visible search number at most k, and monotone connected visible search number >k [Copyright &y& Elsevier]