The hardness of the independence and matching clutter of a graph
Vahan V. Mkrtchyan
Vahe L. Musoyan
Abstract. A clutter (or antichain or Sperner family) \(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 hardness of an edge \(e\) of a clutter is the ratio of the size of \(e\)'s smallest recognizing subset to the size of \(e\). The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs.
Keywords: clutter, hardness, independent set, maximal independent set, matching, maximal matching.
Mathematics Subject Classification: 05C69, 05C70, 05C15.
Cite this article as:
Sasun Hambardzumyan, Vahan V. Mkrtchyan, Vahe L. Musoyan, Hovhannes Sargsyan, The hardness of the independence and matching clutter of a graph
, Opuscula Math. 36
, no. 3 (2016), 375-397, http://dx.doi.org/10.7494/OpMath.2016.36.3.375 Download this article's citation as: a .bib file (BibTeX)
, a .ris file (RefMan)
, a .enw file (EndNote)
or export to RefWorks