### Book

## Optimization Problems in Graph Theory

This book presents open optimization problems in graph theory and networks. Each chapter reflects developments in theory and applications based on Gregory Gutin’s fundamental contributions to advanced methods and techniques in combinatorial optimization.

Researchers, students, and engineers in computer science, big data, applied mathematics, operations research, algorithm design, artificial intelligence, software engineering, data analysis, industrial and systems engineering will benefit from the state-of-the-art results presented in modern graph theory and its applications to the design of efficient algorithms for optimization problems.

Topics covered in this work include:

· Algorithmic aspects of problems with disjoint cycles in graphs

· Graphs where maximal cliques and stable sets intersect

· The maximum independent set problem with special classes

· A general technique for heuristic algorithms for optimization problems

· The network design problem with cut constraints

· Algorithms for computing the frustration index of a signed graph

· A heuristic approach for studying the patrol problem on a graph

· Minimum possible sum and product of the proper connection number

· Structural and algorithmic results on branchings in digraphs

· Improved upper bounds for Korkel--Ghosh benchmark SPLP instances

We say that a graph *G* has the CIS-property and call it a CIS-graph if every maximal clique and every maximal stable set of *G* intersects.

By definition, *G* is a CIS-graph if and only if the complementary graph \(\overline {G}\) is a CIS-graph. Let us substitute a vertex *v* of a graph *G′* by a graph *G*″ and denote the obtained graph by *G*. It is also easy to see that *G* is a CIS-graph if and only if both *G′* and *G*″ are CIS-graphs. In other words, CIS-graphs respect complementation and substitution. Yet, this class is not hereditary, that is, an induced subgraph of a CIS-graph may have no CIS-property. Perhaps, for this reason, the problems of efficient characterization and recognition of CIS-graphs are difficult and remain open. In this paper we only give some necessary and some sufficient conditions for the CIS-property to hold.

There are obvious sufficient conditions. It is known that *P*4-free graphs have the CIS-property and it is easy to see that *G* is a CIS-graph whenever each maximal clique of *G* has a simplicial vertex. However, these conditions are not necessary.

There are also simple necessary conditions. Given an integer *k* ≥ 2, a *comb* (or *k*-*comb*) *S**k* is a graph with 2*k* vertices *k* of which, *v*1, …, *v**k*, form a clique *C*, while others, \(v^{\prime }_1, \ldots , v^{\prime }_k,\) form a stable set *S*, and \((v_i,v^{\prime }_i)\) is an edge for all *i* = 1, …, *k*, and there are no other edges. The complementary graph \(\overline {S_k}\) is called an *anti-comb* (or *k*-anti-comb). Clearly, *S* and *C* switch in the complementary graphs. Obviously, the combs and anti-combs are not CIS-graphs, since *C* ∩ *S* = ∅. Hence, if a CIS-graph *G* contains an induced comb or anti-comb, then it must be settled, that is, *G* must contain a vertex *v* connected to all vertices of *C* and to no vertex of *S*. For *k* = 2 this observation was made by Claude Berge in 1985. However, these conditions are only necessary.

The following sufficient conditions are more difficult to prove: *G* is a CIS-graph whenever *G*contains no induced 3-combs and 3-anti-combs, and every induced 2-comb is settled in *G*, as it was conjectured by Vasek Chvatal in early 90s. First partial results were published by his student Wenan Zang from Rutgers Center for Operations Research. Then, the statement was proven by Deng, Li, and Zang. Here we give an alternative proof, which is of independent interest; it is based on some properties of the product of two Petersen graphs.

It is an open question whether *G* is a CIS-graph if it contains no induced 4-combs and 4-anti-combs, and all induced 3-combs, 3-anti-combs, and 2-combs are settled in *G*.

We generalize the concept of CIS-graphs as follows. For an integer *d* ≥ 2 we define a *d*-*graph* \(\mathcal {G} = (V; E_1, \ldots , E_d)\) as a complete graph whose edges are colored by *d*colors (that is, partitioned into *d* sets). We say that \(\mathcal {G}\) is a CIS-*d*-graph (has the CIS-*d*-property) if \(\bigcap _{i=1}^d C_i \neq \emptyset \) whenever for each *i* = 1, …, *d* the set *C**i* is a maximal color *i*-free subset of *V* , that is, (*v*, *v′*)∉*E**i* for any *v*, *v′*∈ *C**i*. Clearly, in case *d* = 2 we return to the concept of CIS-graphs. (More accurately, CIS-2-graph is a pair of two complementary CIS-graphs.) We conjecture that each CIS-*d*-graph is a Gallai graph, that is, it contains no triangle colored by 3 distinct colors. We obtain results supporting this conjecture and also show that if it holds then characterization and recognition of CIS-*d*-graphs are easily reduced to characterization and recognition of CIS-graphs.

We also prove the following statement. Let \(\mathcal {G} = (V; E_1, \ldots , E_d)\) be a Gallai *d*-graph such that at least *d* − 1 of its *d* chromatic components are CIS-graphs, then \(\mathcal {G}\) has the CIS-*d*-property. In particular, the remaining chromatic component of \(\mathcal {G}\) is a CIS-graph too. Moreover, all 2*d* unions of *d* chromatic components of \(\mathcal {G}\) are CIS-graphs.

In this paper, we consider the minimizing total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine. This problem is known to be open. Here, we give some properties of optimal schedules for the problem and its special cases.

Consideration was given to a graphic realization of the method of dynamic programming. Its concept was demonstrated by the examples of the partition and knapsack problems. The proposed method was compared with the existing algorithms to solve these problems.

Data Correcting Algorithms in Combinatorial Optimization focuses on algorithmic applications of the well known polynomially solvable special cases of computationally intractable problems. The purpose of this text is to design practically efficient algorithms for solving wide classes of combinatorial optimization problems. Researches, students and engineers will benefit from new bounds and branching rules in development efficient branch-and-bound type computational algorithms. This book examines applications for solving the Traveling Salesman Problem and its variations, Maximum Weight Independent Set Problem, Different Classes of Allocation and Cluster Analysis as well as some classes of Scheduling Problems. Data Correcting Algorithms in Combinatorial Optimization introduces the data correcting approach to algorithms which provide an answer to the following questions: how to construct a bound to the original intractable problem and find which element of the corrected instance one should branch such that the total size of search tree will be minimized. The PC time needed for solving intractable problems will be adjusted with the requirements for solving real world problems.

Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph.

Li and Quan, 2010, AAAI Conference, p. 128–133 describe a way to compute even tighter bounds by reducing each colored subproblem to maximum satisfiability problem (MaxSAT). Moreover they show empirically that the new bounds obtained may be lower than the chromatic number.

Based on this idea this paper shows an efficient way to compute related “infra-chromatic” upper bounds without an explicit MaxSAT encoding. The reported results show some of the best times for a stand-alone computer over a number of instances from standard benchmarks.

Let k be a field of characteristic zero, let G be a connected reductive algebraic group over k and let g be its Lie algebra. Let k(G), respectively, k(g), be the field of k- rational functions on G, respectively, g. The conjugation action of G on itself induces the adjoint action of G on g. We investigate the question whether or not the field extensions k(G)/k(G)^G and k(g)/k(g)^G are purely transcendental. We show that the answer is the same for k(G)/k(G)^G and k(g)/k(g)^G, and reduce the problem to the case where G is simple. For simple groups we show that the answer is positive if G is split of type A_n or C_n, and negative for groups of other types, except possibly G_2. A key ingredient in the proof of the negative result is a recent formula for the unramified Brauer group of a homogeneous space with connected stabilizers. As a byproduct of our investigation we give an affirmative answer to a question of Grothendieck about the existence of a rational section of the categorical quotient morphism for the conjugating action of G on itself.

Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny Ĝ → G is bijective; this answers Grothendieck's question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg's theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G]G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G]G and that of the representation ring of G and answer two Grothendieck's questions on constructing generating sets of k[G]G. We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T- - - >G/T where T is a maximal torus of G and W the Weyl group.