Contraction obstructions for connected graph searching

DOI10.1016/J.DAM.2015.07.036MaRDI QIDQ298950zbMATHOpenAlexFDO

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)

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

zbMATH Keywords

graph contractionsgraph searchingobstruction set

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(9)

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

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)