### The complexity of some graph problems with bounded minors of their constraint matrices

#### D. V. Gribanov^{1}, D. S. Malyshev^{2}

Annotation | The article considers natural formulations of the independent set problem, vertex and edge dominating set problems as integer linear programming problems. For every fixed $C$, authors prove polynomial-time solvability of both dominating set problems in a class of graphs, for which all minors of the vertex and edge adjacency matrices are at most $C$ in the absolute value. The paper also includes a similar result for the independent set problem and for a class of graphs, which is defined by bounding of absolute values of all matrix minors obtained by augmenting of transposed incidence matrices by all-ones vectors. |
---|---|

Keywords | boolean linear programming, independent set problem, dominating set problem, matrix minor, polynomial-time algorithm |

^{1}Assistant lecturer of Department of Algebra, Geometry and Discrete Mathematics, Lobachevsky State University, Nizhny Novgorod; dimitry.gribanov@gmail.com^{2}Professor of Department of Applied Mathematics and Informatics, National Research University Higher School of Economics, Nizhny Novgorod; dsmalyshev@rambler.ru

**Citation**: D. V. Gribanov, D. S. Malyshev, "[The complexity of some graph problems with bounded minors of their constraint matrices]", Zhurnal Srednevolzhskogo matematicheskogo obshchestva,18:3 (2016) 19–31 (In Russian)