### ?

## Critical hereditary graph classes: a survey

Optimization Letters. 2016. Vol. 10. No. 8. P. 1593-1612.

The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called “critical” graph classes, which play an important role in the complexity analysis for the family. Recent progress in studying such classes is presented in the article.

Language:
English

Malyshev D., Razvenskaya O., Discrete Applied Mathematics 2017 Vol. 219 P. 158-166

We show that the chromatic number of {P_5,K_p-e}-free graphs can be computed in polynomial time for each fixed p.
Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for {P_5,co(P_3+P_2)}-free graphs. ...

Added: November 21, 2016

Malyshev D., Discrete Applied Mathematics 2016 Vol. 203 P. 117-126

We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices. ...

Added: October 9, 2015

Malyshev D., Discrete Applied Mathematics 2018 Vol. 247 P. 423-432

We show that the weighted coloring problem can be solved for {P5,banner}-free graphs and for {P5,dart}-free graphs in polynomial time on the sum of vertex weights. ...

Added: April 23, 2018

Malyshev D., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. ...

Added: April 7, 2014

Malyshev D., The coloring problem for classes with two small obstructions / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.

The coloring problem is studied in the paper for graph classes deﬁned by two small forbidden induced subgraphs. We prove some suﬃcient conditions for eﬀective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most ﬁve vertices except ...

Added: October 3, 2013

Gribanov D., Malyshev D., Discrete Applied Mathematics 2017 Vol. 227 P. 13-20

We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with (augmented) constraint matrices having bounded minors in the absolute value ...

Added: April 23, 2017

Malyshev D., Journal of Applied and Industrial Mathematics 2014 Vol. 8 No. 2 P. 245-255

The edge list-ranking problem is a generalization of the classical edge coloring problem, and it is a mathematical model for some parallel processes. The computational complexity of this problem is under study for graph sets closed under isomorphism and deletion of vertices (hereditary classes). Allfinitely defined and minor-closed cases are described for which the problem ...

Added: May 8, 2014

Malyshev D., Graphs and Combinatorics 2017 Vol. 33 No. 4 P. 1009-1022

We completely determine the complexity status of the vertex 3-colorability problem for the problem restricted to all hereditary classes defined by at most 3 forbidden induced subgraphs each on at most 5 vertices. We also present a complexity dichotomy for the problem and the family of all hereditary classes defined by forbidding an induced bull ...

Added: May 26, 2017

Malyshev D., Journal of Applied and Industrial Mathematics 2013 Vol. 7 No. 3 P. 412-419

The notion is introduced of an expanding operator for the independent set problem. This notion is a useful tool for the constructive formation of new cases with the efficient solvability of the problem in the family of hereditary classes of graphs and is applied to hereditary parts of the set Free({P_5,C_5}). It is proved that ...

Added: October 3, 2013

Malyshev D., Journal of Combinatorial Optimization 2017 Vol. 33 No. 3 P. 809-813

We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the ...

Added: March 17, 2016

Malyshev D., Journal of Applied and Industrial Mathematics 2013 Vol. 7 No. 4 P. 537-548

We prove the polynomial solvability of the independent set problem for some family of
classes of the planar subcubic graphs. ...

Added: January 21, 2014

Gribanov D., Malyshev D., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19-31

Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...

Added: October 20, 2016

Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64

An algorithm is implemented in the article for finding the independence number of a n-vertex graph from the class Free({P5,C5, Kp}) in time O(np+O(1)). ...

Added: June 6, 2012

Malyshev D., Siberian Electronic Mathematical Reports 2014 Vol. 11 P. 811-822

We obtain a complete complexity dichotomy for the edge 3- colorability within the family of hereditary classes defined by forbidden
induced subgraphs on at most 6 vertices and having at most two 6-vertex forbidden induced structures. ...

Added: April 7, 2014

Malyshev D., Journal of Combinatorial Optimization 2016 Vol. 31 No. 2 P. 833-845

The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of the problem for two of the mentioned 13 classes. ...

Added: September 18, 2014

Malyshev D., Journal of Combinatorial Optimization 2016 Vol. 32 No. 1 P. 226-243

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with ...

Added: April 4, 2015

Malyshev D., Journal of Applied and Industrial Mathematics 2012 Vol. 6 No. 1 P. 97-99

Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs, On the other ...

Added: December 7, 2012

Malyshev D., Optimization Letters 2014 Vol. 8 No. 8 P. 2261-2270

The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except ...

Added: March 6, 2014

Malyshev D., Gribanov D., Discrete Optimization 2018 Vol. 29 P. 103-110

We consider boolean linear programming formulations of the vertex and edge dominating set problems and prove their polynomial-time solvability for classes of graphs with constraint matrices having bounded minors in the absolute value. ...

Added: April 8, 2018

Goldengorin B. I., Malyshev D., Pardalos P. M., Doklady Mathematics 2013 Vol. 87 No. 3 P. 368-371

The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and ...

Added: June 23, 2013

Gafarov E., Dolgui A., Lazarev A. A., Two-Station Single-Track Railway Scheduling Problem With Trains of Equal Speed / Elsevier. Series -- "Computers & Industrial Engineering". 2014.

In this paper, the single-track railway scheduling problem with two stations and several segments of the track is considered. Two subsets of trains are given, where trains from the first subset go from the first station to the second station, and trains from the second subset go in the opposite direction. The speed of trains ...

Added: April 10, 2015

Malyshev D., Journal of Applied and Industrial Mathematics 2020 Vol. 14 No. 4 P. 706-721

The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...

Added: January 30, 2021

Grines V., Malyshev D., Pochinka O. et al., Regular and Chaotic Dynamics 2016 Vol. 21 No. 2 P. 189-203

It is well known that the topological classification of structurally stable flows on surfaces as well as the topological classification of some multidimensional gradient-like systems can be reduced to a combinatorial problem of distinguishing graphs up to isomorphism. The isomorphism problem of general graphs obviously can be solved by a standard enumeration
algorithm. However, an efficient ...

Added: April 5, 2016

Malyshev D., Optimization Letters 2021 Vol. 15 No. 2 P. 311-326

The vertex colourability problem is to determine, for a given graph and a given natural k, whether it is possible to split the graph’s vertex set into at most k subsets, each of pairwise non-adjacent vertices, or not. A hereditary class is a set of simple graphs, closed under deletion of vertices. Any such a class can be ...

Added: January 6, 2021