Open AccessA constructive existence theorem related to local transformations of graphs for the independent set problem
Author(s) -
Сироткин Дмитрий Валерьевич,
Малышев Дмитрий Сергеевич
Publication year - 2019
Publication title -
žurnal srednevolžskogo matematičeskogo obŝestva
Language(s) - English
Resource type - Journals
eISSN - 2587-7496
pISSN - 2079-6900
DOI - 10.15507/2079-6900.21.201902.215-221
Subject(s) - mathematics , independent set , constructive , combinatorics , split graph , maximal independent set , cograph , pairwise comparison , discrete mathematics , pathwidth , graph , class (philosophy) , power set , constructive proof , set (abstract data type) , indifference graph , line graph , computer science , statistics , process (computing) , artificial intelligence , programming language , operating system
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.