Gadget classification (Q2366217): Difference between revisions

Let \(G\) be a graph and, for each vertex \(v\), let \(B_ v\) be a set of integers between 0 and \(\deg_ G(v)\). A \(B\)-factor of \(G\) is a spanning subgraph \(H\) with each \(\deg_ H(v)\in B_ v\). To decide the existence of \(B\)-factors is NP-complete in general, but polynomial if no \(B_ v\) contains a gap of more than one element (cf. \textit{L. Lovász} and \textit{M. Plummer} [Matching theory (1986; Zbl 0618.05001)] and \textit{G. Cornuejols} [Carnegie Mellon Management Science Research Report MSRR 528 (1986)]. It was observed by Pulleyblank that for certain restricted types of \(B_ v\)'s, the problem of existence of \(B\)-factors can be reduced to another factor problem---that of finding a spanning subgraph of a given graph in which all components are either edges or triangles (from a given family of triangles). This problem is known to be solvable in polynomial time, cf. \textit{G. Cornuejols}, \textit{D. Hartvigsen} and \textit{W. Pulleyblank} [Oper. Res. Lett. 1, 139-143 (1982; Zbl 0488.90070)], or \textit{P. Hell} and \textit{D. G. Kirkpatrick} [Algebraic methods in graph theory, Vol. I, Conf. Szeged 1978, Colloq. Math. Soc. János Bolyai 25, 273-279 (1981; Zbl 0474.05054) and Discrete Math. 49, 45-59 (1984; Zbl 0582.05046)]. The `gadgets' in the title of this paper refer to the modules used in that reduction. Pulleyblank asked exactly which sets \(B_ v\) allow such a reduction, i.e., admit a gadget. Cornuejols found this to be the case if \(B_ v\) has no gaps (the set is an interval of consecutive integers) or if the gap is just the second element (or the next to last element) of an interval. The present author shows that this is so also if \(B_ v\) is an interval with both the second and the next to last element removed; he also shows that gadgets do not exist for any of the other types of sets \(B_ v\).