A set of edges of a hypergraph H is an algebraic set if its characteristic vector can be expressed as a linear combination of rows of the (node-edge) incidence matrix of H . Recently it was proven that deciding whether or not a given edge-set of H contains a non-empty algebraic set is an NP -complete problem. In this paper we give a linear time algorithm to decide if a given edge-set contains a non-empty algebraic set when the hypergraph is a graph.
展开▼