Opuscula Math. 36, no. 3 (2016), 375-397
http://dx.doi.org/10.7494/OpMath.2016.36.3.375

Opuscula Mathematica

The hardness of the independence and matching clutter of a graph

Sasun Hambardzumyan
Vahan V. Mkrtchyan
Vahe L. Musoyan
Hovhannes Sargsyan

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.

Full text (pdf)