The complexity of the independence and matching clutter of a graph
Sasun Hambartsumyan, Vahan Mkrtchyan, Vahe L. Musoyan, Hovhannes Sargsyan · arXiv (Cornell University) · 2009
A clutter $L$ is a pair $(V,E)$, where $V$ is a finite set and $E$ is a family of subsets of $V$ none of which is a subset of another. Usually, the elements of $V$ are called vertices of $L$, and the elements of $E$ are called edges of $L$. A subset $s_e$ of an edge $e$ of a clutter is called recognizing for $e$, if $s_e$ is not a subset of another edge. The complexity of an edge $e$ of a clutter is the ratio of the size of $e\textrm{'s}$ smallest recognizing subset to the size of $e$. The complexity of a clutter is the maximum of the complexities of its edges. We study the complexity of clutters arising from independent sets and matchings of graphs.