Search

After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover Number . Here we consider the treewidth and pathwidth problems parameterized by k , the size of a minimum vertex cover of the input graph. We show that the pathwidth and treewidth can be computed in O ∗ ( 3 k ) time. This complements recent polynomial kernel results for treewidth and pathwidth parameterized by the Vertex Cover Number . [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]

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]

Abstract: Let be a finite, simple and undirected graph. For , let be the edge boundary of . Given an integer , , let the edge isoperimetric value of at be defined as . The edge isoperimetric peak of is defined as . Let denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete -ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete -ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth (denoted as ), and where , are constants. For a complete -ary tree of depth (denoted as ) and where is a constant, we show that and where , are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete -ary tree. Let be a finite, connected and rooted tree — the root being the vertex . Define a weight function where the weight of a vertex is the number of its successors (including itself) and let the weight index be defined as the number of distinct weights in the tree, i.e . For a positive integer , let . We show that . [Copyright &y& Elsevier]

Abstract: The d-dimensional hypercube, , is the graph on vertices, which correspond to the d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by ) generalizes the notion of hypercubes: The vertices correspond to the d-vectors where the components are from the set , and two of the vertices are adjacent if and only if the corresponding vectors differ in exactly one component. In this paper we show that the and the . [Copyright &y& Elsevier]

It is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant w can be characterized by a finite obstruction set obs(TW(w)) (resp. obs(PW(w))). These obstruction sets are known for w⩽3 so far. In this paper we give a structural characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with a fixed number of vertices in terms of subgraphs of the complement. Our approach also essentially simplifies known characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with (w+3) vertices.Also for any w⩾3 a graph from obs(TW(w))&z.drule;obs(PW(w)) is constructed, that solves an open problem. [Copyright &y& Elsevier]