Contraction obstructions for connected graph searching

DOI10.1016/J.DAM.2015.07.036zbMATH Open1339.05210arXiv1410.8756OpenAlexW1717727751MaRDI QIDQ298950FDOQ298950

Authors: Micah J. Best, Arvind Kumar Gupta, Dimitrios M. Thilikos, Dimitris Zoros 

Publication date: 21 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We consider the connected variant of the classic mixed search game where, in each search step, cleaned edges form a connected subgraph. We consider graph classes with bounded connected (and monotone) mixed search number and we deal with the question whether the obstruction set, with respect of the contraction partial ordering, for those classes is finite. In general, there is no guarantee that those sets are finite, as graphs are not well quasi ordered under the contraction partial ordering relation. In this paper we provide the obstruction set for $k=2$, where $k$ is the number of searchers we are allowed to use. This set is finite, it consists of 177 graphs and completely characterises the graphs with connected (and monotone) mixed search number at most 2. Our proof reveals that the "sense of direction" of an optimal search searching is important for connected search which is in contrast to the unconnected original case. We also give a double exponential lower bound on the size of the obstruction set for the classes where this set is finite.

Full work available at URL: https://arxiv.org/abs/1410.8756

Recommendations

• Searching is not jumping.
• Connected graph searching
• Connected search for a lazy robber
• Mixed searching and proper-path-width
• Monotony Properties of Connected Visible Graph Searching

zbMATH Keywords

graph contractionsgraph searchingobstruction set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Cites Work

• Graph searching and a min-max theorem for tree-width
• Graph minors. XX: Wagner's conjecture
• Graph minors. XIII: The disjoint paths problem
• An annotated bibliography on guaranteed graph searching
• Graph minors. II. Algorithmic aspects of tree-width
• Recontamination does not help to search a graph
• Graph minors. I. Excluding a forest
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Obstruction set isolation for the gate matrix layout problem
• Fugitive-search games on graphs and related parameters
• On the monotonicity of games generated by symmetric submodular functions.
• Algorithms and obstructions for linear-width and related search parameters
• Monotony Properties of Connected Visible Graph Searching
• Monotonicity in graph searching
• From pathwidth to connected pathwidth
• Parameterized and Exact Computation
• Searching is not jumping.
• Connected graph searching

Cited In (9)

• Title not available (Why is that?)
• On-line search in two-dimensional environment
• Four-searchable biconnected outerplanar graphs
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Finding small-width connected path decompositions in polynomial time
• A connected version of the graph coloring game
• Connected graph searching for unicyclic graphs
• Sparse obstructions for minor-covering parameters
• Connected search for a lazy robber

This page was built for publication: Contraction obstructions for connected graph searching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q298950)