Search

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. Ordered pathwidth is roughly the same as proof space and the ordered treewidth of a proof is meant to serve as a measure of how far it is from being treelike. Length-space lower bounds for k -DNF refutations are generalized to arbitrary infinity axioms and strengthened in that the space measure is relaxed to ordered treewidth. [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]

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]

We describe an O(nlogn) algorithm for the computation of the vertex separation of unicyclic graphs. The algorithm also computes a linear layout with optimal vertex separation in the same time bound. Pathwidth, node search number and vertex separation are different ways of defining the same notion. Path decompositions and search strategies can be derived from linear layouts. The algorithm applies existing, linear time, techniques for the computation of the vertex separation of trees together with corresponding optimal layouts. We reformulate the earlier work on the linear time computation of optimal layouts. A polynomial time algorithm for the problem on unicyclic graphs can be inferred from existing more general methods for graphs of fixed treewidth, since unicyclic graphs have treewidth two, but the time complexity of the resulting method would seem to be an inordinately high order polynomial. Our algorithm we claim is “practical.” The addition of one edge to a tree does seem to require a considerably more elaborate algorithm. [Copyright &y& Elsevier]