?
An intractability result for the vertex 3-colourability problem
Optimization Letters. 2022. Vol. 16. P. 1403-1409.
Malyshev D. S., Приставченко О. В.
The vertex 3-colourability problem is to decide whether the vertex set of a given graph
can be split into three subsets of pairwise non-adjacent vertices. This problem is known
to be NP-complete in a certain class of graphs, defined by an explicit description of
allowed 5-vertex induced subgraphs in them. In the present paper, we improve this
result by showing that the vertex 3-colourability problem remains NP-complete for a
reduced set of allowed 5-vertex induced structures. It gives a step towards obtaining a
complete complexity dichotomy for thementioned problem and all the classes, defined
by 5-vertex forbidden induced prohibitions.
Publication based on the results of:
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
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
Sirotkin D., Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 4 P. 759-769
The 3-coloring problem for a given graph consists in verifying whether it is possible
to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete
complexity classification is known for this problem for the hereditary classes defined by triples of
forbidden induced subgraphs, each on at most 5 vertices. In this article, ...
Added: November 20, 2018
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., Дискретный анализ и исследование операций 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., Journal of Combinatorial Optimization 2014 Vol. 27 No. 2 P. 345-354
The notion of a boundary graph class was recently introduced for a classification of hereditary graph classes according to the complexity of a considered problem. Two concrete graph classes are known to be boundary for several graph problems. We formulate a criterion to determine whether these classes are boundary for a given graph problem or ...
Added: February 7, 2013
Artale A., Kontchakov R., Ryzhikov V. et al., ACM Transactions on Computational Logic 2014 Vol. 15 No. 3 P. 25.1-25.50
We design temporal description logics (TDLs) suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Lite logics with three types of concept inclusions (ranging from atomic concept inclusions and disjointness to the full Booleans), as well as cardinality constraints and role inclusions. The logics are interpreted ...
Added: March 25, 2015
Malyshev D., Pardalos P. M., 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
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
Kazda A., Opršal J., Valeriote M. et al., Canadian Mathematical Bulletin 2020 P. 577-591
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation m that satisfies the minority equations m(y,x,x)≈m(x,y,x)≈m(x,x,y)≈y . We show that a common polynomial-time approach to testing for this type of condition will not work in this case and that this decision problem lies in the class NP. ...
Added: June 15, 2020
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
Kochergin V., Moscow University Mathematics Bulletin 2022 Vol. 77 No. 3 P. 113-119
Abstract: The computational complexity of the element (Formula presented.) of the Abelian group (Formula presented.) (it is supposed that kii for all i) and the computational complexity of the term (Formula presented.) are compared in the paper. The computational complexity means the minimal possible number of multiplication operations, and all the results of intermediate multiplications ...
Added: October 29, 2022
Gafarov E., Dolgui A., Lazarev A. A., / 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., Pardalos P. M., Optimization Letters 2015 Vol. 9 No. 5 P. 839-843
The quadratic programming problem is known to be NP-hard for Hessian matrices with only one negative eigenvalue, but it is tractable for convex instances. These facts yield to consider the number of negative eigenvalues as a complexity measure
of quadratic programs. We prove here that the clique problem is tractable for two variants of its Motzkin-Strauss ...
Added: September 26, 2014
Malyshev D., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791-801
For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain ...
Added: February 16, 2024
Malyshev D., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.
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: October 3, 2013
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by ...
Added: June 23, 2013
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
Kontchakov R., Pratt-Hartmann I., Nenov Y. et al., ACM Transactions on Computational Logic 2013 Vol. 14 No. 2 P. 13.1-13.48
We consider the quantifier-free languages, Bc and Bc°, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of being connected, and the property of having a connected interior. These languages are interpreted over the regular closed sets of Rn (n ≥ 2) and, additionally, over the regular closed ...
Added: March 25, 2015
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
Shvydun S., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Two-stage superposition choice procedures, which sequentially apply two choice procedures so that the result of the first choice procedure is the input for the second choice procedure, are studied. We define which of them satisfy given normative conditions, showing how a final choice is changed due to the changes of preferences or a set of ...
Added: October 20, 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., 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
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