Geodesic
The complexity of some graph problems with bounded minors of their constraint matrices
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 18 (2016) no. 3, pp. 19-31.

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Mots-clés : matrix minor, polynomial-time algorithm. 
@article{SVMO_2016_18_3_a1,
     author = {D. V. Gribanov and D. S. Malyshev},
     title = {The complexity of some graph problems with bounded minors of their constraint matrices},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {19--31},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2016_18_3_a1/}
}
TY  - JOUR
AU  - D. V. Gribanov
AU  - D. S. Malyshev
TI  - The complexity of some graph problems with bounded minors of their constraint matrices
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2016
SP  - 19
EP  - 31
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2016_18_3_a1/
LA  - ru
ID  - SVMO_2016_18_3_a1
ER  - 
%0 Journal Article
%A D. V. Gribanov
%A D. S. Malyshev
%T The complexity of some graph problems with bounded minors of their constraint matrices
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2016
%P 19-31
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2016_18_3_a1/
%G ru
%F SVMO_2016_18_3_a1
D. V. Gribanov; D. S. Malyshev. The complexity of some graph problems with bounded minors of their constraint matrices. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 18 (2016) no. 3, pp. 19-31. http://geodesic.mathdoc.fr/item/SVMO_2016_18_3_a1/

[1] V. E. Alekseev, D. V. Zakharova, “Independent sets in the graphs with bounded minors of the extended incidence matrix”, Journal of Applied and Industrial Mathematics, 5:1 (2011), 14–18 | DOI | MR

[2] S. Arnborg, A. Proskurowski, “Linear time algorithms for NP-hard problems restricted to partial $k$-trees”, Discrete Applied Mathematics, 23:1 (1989), 11–-24 | DOI | MR | Zbl

[3] S. Artmann, F. Eisenbrand, C. Glanzer, T. Oertel, S. Vempala, R. Weismantel, A note on non-degenerate integer programs with small sub-determinants, arXiv: 1603.09595v1 | MR

[4] R. Boliac, V. Lozin, “On the clique-width of graphs in hereditary classes”, Lecture Notes in Computer Science, 2518, 2002, 44–54 | DOI | MR | Zbl

[5] A. Brandstädt, F. F. Dragan, “On linear and circular structure of (claw, net)-free graphs”, Discrete Applied Mathematics, 129:2–3 (2003), 285–303 | DOI | MR | Zbl

[6] B. Courcelle, J. Makowsky, U. Rotics, “Linear time solvable optimization problems on graphs of bounded clique-width”, Theory of Computing Systems, 33:2 (2000), 125–150 | DOI | MR | Zbl

[7] R. M. Gray, “Toeplitz and circulant matrices: a review”, Foundations and Trends in Communications and Information Theory, 2:3 (2006), 155–239 | DOI

[8] N. Karmarkar, “A new polynomial time algorithm for linear programming”, Combinatorica, 4:4 (1984), 373–395 | DOI | MR | Zbl

[9] L. G. Khachiyan, “Polynomial algorithms in linear programming”, USSR Computational Mathematics and Mathematical Physics, 20:1 (1980), 53–72 | DOI | MR | Zbl

[10] D. Kobler, U. Rotics, “Edge dominating set and colorings on graphs with fixed clique-width”, Discrete Applied Mathematics, 126:2–3 (2003), 197–221 | DOI | MR | Zbl

[11] Y. E. Nesterov, A. S. Nemirovsky, Interior point polynomial methods in convex programming, SIAM, 1994 | MR

[12] P. M. Pardalos, C. G. Han, Y. Ye, “Interior point algorithms for solving nonlinear optimization problems”, COAL Newsletter, 19 (1991), 45–54

[13] B. Reed, “Mangoes and Blueberries”, Combinatorica, 19:2 (1999), 267–296 | DOI | MR | Zbl

[14] V. N. Shevchenko, Qualitative topics in integer linear, AMS, 1997 | MR

[15] S. I. Veselov, A. J. Chirkov, “Integer program with bimodular matrix”, Discrete Optimization, 6:2 (2009), 220–222 | DOI | MR | Zbl

[16] S. H. Whitesides, “A method for solving certain graph recognition and optimization problems, with applications to perfect graphs.”, Annals of Discrete Mathematics, 88 (1984), 281–297 | MR