The complexity of the positive semidefinite zero forcing

DOI10.1007/978-3-319-12691-3_51MaRDI QIDQ2942442zbMATH OpenOpenAlexFDO

Authors Shaun M. Fallat, K. Meagher, Boting Yang

Publication date 11 September 2015

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: The positive zero forcing number of a graph is a graph parameter that arises from a non-traditional type of graph colouring, and is related to a more conventional version of zero forcing. We establish a relation between the zero forcing and the fast-mixed searching, which implies some NP-completeness results for the zero forcing problem. For chordal graphs much is understood regarding the relationships between positive zero forcing and clique coverings. Building upon constructions associated with optimal tree covers and forest covers, we present a linear time algorithm for computing the positive zero forcing number of chordal graphs. We also prove that it is NP-complete to determine if a graph has a positive zero forcing set with an additional property.

Recommendations

• On the complexity of the positive semidefinite zero forcing number
• Positive semidefinite zero forcing: complexity and lower bounds
• Lower bounds for positive semidefinite zero forcing and their applications
• Positive semidefinite zero forcing
• Positive semidefinite zero forcing numbers of two classes of graphs

Cites work

• Fast-mixed searching and related problems on graphs
• Monotonicity in graph searching
• Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees
• On the Fast Searching Problem
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• On the fractional intersection number of a graph
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Positive semidefinite zero forcing
• Searching and pebbling
• The complexity of searching a graph
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited in

(6)

• Positive zero forcing and edge clique coverings
• Compressed cliques graphs, clique coverings and positive zero forcing
• On the complexity of failed zero forcing
• On the complexity of the positive semidefinite zero forcing number
• Positive semidefinite zero forcing: complexity and lower bounds
• Lower bounds for positive semidefinite zero forcing and their applications

This page was built for publication: The complexity of the positive semidefinite zero forcing

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