2016/09/01 by Shitov, Yaroslav · 6 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1609.00211
Let G be a simple graph whose vertices are partitioned into two subsets, called filled vertices and empty vertices. A vertex v is said to be forced by a filled vertex u if v is a unique empty neighbor of u. If we can fill all the vertices of G by repeatedly filling the forced ones, then we call an initial set of filled vertices a forcing set. We discuss the so-called failed forcing number of a graph, which is the largest cardinality of a set which is not forcing. Answering the recent question of Ansill, Jacob, Penzellna, Saavedra, we prove that this quantity is NP-hard to compute. Our proof also works for a related graph invariant which is called the skew failed forcing number.