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.
- J.C. Claussen, Offdiagonal complexity: A computationally quick complexity measure for graphs and networks, Physica A 375 (2007), 365-373.
- G. Cornuejols, Combinatorial Optimization: Packing and Covering, SIAM (January, 2001).
- M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of \(NP\)-completeness, Freeman, 1979.
- S. Jukna, On graph complexity, ECCC Report, No. 5, 2004.
- L. Lovász, M.D. Plummer, Matching theory, Ann. Discrete Math. 29 (1986).
- D.P. Sumner, Randomly matchable graphs, J. Graph Theory 3 (1979), 183-186.
- D.B. West, Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, 1996.
- Sasun Hambardzumyan
- Department of Informatics and Applied Mathematics, Yerevan State University, Yerevan, 0025, Armenia
- Vahan V. Mkrtchyan
- Institute for Informatics and Automation Problems, National Academy of Sciences of Republic of Armenia, 0014, Armenia
- Vahe L. Musoyan
- Stanford University, Computer Science Department, Stanford, CA 94305, USA
- Hovhannes Sargsyan
- Department of Informatics and Applied Mathematics, Yerevan State University, Yerevan, 0025, Armenia
- Communicated by Mariusz Meszka.
- Received: 2014-03-30.
- Revised: 2015-12-01.
- Accepted: 2015-12-17.
- Published online: 2016-02-21.
