### ?

## A complexity dichotomy for the dominating set problem

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.

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 ...

Added: December 18, 2015

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

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

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

Дискретная математика 2012 Т. 24 № 2 С. 75-78

В данной работе исследуются семейства граничных классов для задач о вершинной k-раскраске и о хроматическом числе. Указано континуальное семейство классов графов, являющихся граничными одновременно для первой задачи при k=3 и для второй. Для любого k>3 выявлено континуальное семейство граничных классов для первой задачи, не являющихся граничными для второй. Для задачи о хроматическом числе найден граничный ...

Added: November 30, 2012

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

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

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

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

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

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

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

Added: October 20, 2016

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

Theoretical Computer Science 2011 No. 412 P. 3545-3554

The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle ...

Added: September 11, 2012

Journal of Applied and Industrial Mathematics 2017 Vol. 11 No. 1 P. 99-106

The notions of boundary and minimal hard classes of graphs, united by the term “critical classes”, are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the ...

Added: February 13, 2017

Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48

Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...

Added: November 30, 2012

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

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

American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77

We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...

Added: February 23, 2016

, in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Vol. 10846.: Springer, 2018.. P. 295-307.

We consider a computational model which is known as set automata.
The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].
In this ...

Added: June 21, 2018

Linear Algebra and its Applications 2013 Vol. 439 No. 8 P. 2500-2502

We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute. ...

Added: August 11, 2013

Journal of Logic and Computation 2021 Vol. 31 No. 2 P. 426-443

It is shown that products and expanding relativized products of propositional modal logics where one component is the minimal monomodal logic K are polynomial-time reducible to their single-variable fragments. Therefore, the nown lower bound complexity and undecidability results for such logics are extended to their single-variable fragments. Similar results are obtained for products where one component is a polymodal logic with a K-style ...

Added: September 24, 2020

, in: 2019 XVI International Symposium "Problems of Redundancy in Information and Control Systems" (REDUNDANCY). .: IEEE, 2019.. P. 115-116.

This article is dedicated to an alternative method of solving of the Chinese Remainder Theorem for polynomials. To construct the solution, a system of linear equations is constructed (using the method of undetermined coefficients) and then solved. The complexity of the proposed method is also calculated. ...

Added: October 27, 2019

, in: 6th International Conference on Computers Communications and Control (ICCCC) 2016. .: Oradea: Agora University, 2016.. P. 118-123.

The problem of quick detection of central nodes in large networks is studied. There are many measures that allow to evaluate a topological importance of nodes of the network. Unfortunately, most of them cannot be applied to large networks due to their high computational complexity. However, if we narrow the initial network and apply these ...

Added: June 8, 2016

Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205

The vertex 3-colourability problem is to determine for a given graph whether one can divide its vertex set into three subsets of pairwise non-adjacent vertices. This problem is NP-complete in the class of planar graphs, but it becomes polynomial-time solvable for planar triangulations, i.e. planar graphs, all facets of which (including external) are triangles. Additionally, ...

Added: July 2, 2018