zbMATH — the first resource for mathematics

Applicability of vertex replacements for a class of problems on \(K\)- vertex subgraphs. (English. Russian original) Zbl 0828.05059
Russ. Acad. Sci., Dokl., Math. 49, No. 3, 478-483 (1994); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 336, No. 2, 157-160 (1994).
There is a class of problems on graphs for which a condition is stated in the following manner. Let a graph \(G= (V, E)\) and a positive integer \(K\leq |V|\) be given. Does there exist a subset \(V'\subseteq V\) such that \(|V'|\geq K\) \((|V'|\leq K)\) and subgraph \(G'= (V', E')\) has property \(\Pi\)? Property \(\Pi\) for the best-known problems is stated in such phrases as, for example, independent set, dominating set, vertex cover, clique, etc. In addition, there exist many problems, including applied problems, which cannot be reduced to this form. We call the class of problems stated here problems on \(K\)-vertex subgraphs, which belong to the class of NP-complete problems.
In this note, we consider a polynomial search algorithm for the initial subgraph, which, as a calculational experiment showed, in many cases is itself a solution to the problem. We prove that the algorithm for solution of the problem on a star subgraph is polynomial, which allows one to assume the possible future appearance of other problems from this class having polynomial complexity. We consider the new so-called method of vertex replacements. The class of problems on \(K\)-vertex subgraphs has wide applications, including the design and control of flexible manufacturing systems.
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science