MSC2010 05C69
A constructive existence theorem related to local transformations of graphs for the independent set problem
D. V. Sirotkin1, D. S. Malyshev2
| Annotation | For a given graph, the independent set problem is to find the size of a maximum set of pairwise non-adjacent its vertices. There are numerous cases of NP-hardness and polynomial-time solvability of this problem. To determine a computational status of the independent set problem, local transformations of graphs are often used. The paper considers some class of replacements of subgraphs in graphs that change the independence number in a controllable way. Every such local transform of a graph is determined by some pattern which is a subset of the power set. It is obvious that this pattern must be gradable. The paper shows that replacing subgraph exists for any gradable pattern. |
|---|---|
| Keywords | independent set problem, local transformation, graph with given properties |
1
Dmitry V. Sirotkin, Research Intern, Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics (25/12 Bolshaja Pecherskaja St., Nizhny Novgorod 603155, Russia), ORCID: http://orcid.org/0000-0002-2682-9867, dmitriy.v.sirotkin@gmail.com
2Dmitry S. Malyshev, Professor, Department of Applied Mathematics and Information Science,
National Research University Higher School of Economics (25/12 Bolshaja Pecherskaja St., Nizhny Novgorod 603155, Russia),
Professor, Department of Algebra, Geometry and Discrete Mathematics, National Research Lobachevsky University of Nizhny Novgorod
(23 Gagarina Avenue, Nizhny Novgorod, 603950, Russia), D.Sc. (Physics and Mathematics), ORCID: http://orcid.org/0000-0001-7529-8233, dsmalyshev@rambler.ru
Citation: D. V. Sirotkin, D. S. Malyshev, "[A constructive existence theorem related to local transformations of graphs for the independent set problem]", Zhurnal Srednevolzhskogo matematicheskogo obshchestva,21:2 (2019) 215–221 (In Russian)
DOI 10.15507/2079-6900.21.201902.215-221
