Download

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

D. V. Gribanov1, D. S. Malyshev2

AnnotationThe 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.
Keywordsboolean linear programming, independent set problem, dominating set problem, matrix minor, polynomial-time algorithm

1Assistant lecturer of Department of Algebra, Geometry and Discrete Mathematics, Lobachevsky State University, Nizhny Novgorod; dimitry.gribanov@gmail.com

2Professor 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)