On the Computation of the Competition Number of a Graph
Robert J. Opsut · SIAM Journal on Algebraic and Discrete Methods · 1982
This paper examines the problem of recognizing competition graphs (niche overlap graphs), a notion introduced and studied extensively by Cohen [Food Webs and Niche Space, Princeton Univ. Press, Princeton, NJ, 1978]. Beginning with an acyclic digraph $F = ( V,A )$, define its competition graph $K (F ) = ( V,E)$ by $( x,y ) \in E$ if and only if there exists a w such that $( x,w ) \in A$ and $( y,w ) \in A$. A graph, G, is a competition graph if there exists an F such that $G = K ( F )$. Roberts [Lecture Notes in Mathematics 642, Springer-Verlag, New York, 1978, pp. 477–490] studied recognizing competition graphs and, equivalently, computing an arbitrary graphs competition number, $k( G )$. The competition number, which he showed to be well defined, is the smallest k such that $G \cup I_k $ is a competition graph. In this paper we settle a question posed by Roberts and show that recognizing competition graphs is NP-complete by reducing it to R-CONTENT as defined by Orlin [Nederl. Akad. Wetensch. Proc. Ser. A, 80 (1977), pp. 406–424]. We also give bounds on $k ( G )$ in terms of R-Content $( G )$ and compute $k ( G )$ for the class of line graphs using a technique similar to that in Roberts.