The complexity of some graph problems with bounded minors of their constraint matrices
D. V. Gribanov1, D. S. Malyshev2
| 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 |
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)
