An apple Ak is a graph obtained from a chordless cycle Ck of length k ≥ 4 by adding a vertex that has exactly one neighbor on the cycle. A graph is apple-free if it contains no Ak, k ≥ 4, as an induced subgraph. Since every apple contains an induced claw, a chordless cycle of length at least four, and an induced path on four vertices, the class of apple-free graphs generalizes that of claw-free graphs, chordal graphs, and cographs. In this work, we provide an explicit description of the structure of all apple-free graphs.
We study separable plus quadratic (SPQ) polynomials, i.e., polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. We fully characterize when nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative quadratic polynomial, and (ii) a sum of squares of polynomials. We then prove that testing nonnegativity of an SPQ polynomial is NP-hard. By contrast, we show that testing convexity of an SPQ polynomial can be reduced to solving a semidefinite program. Moreover, we show that polynomial optimization problems where the objective and the constraint functions are given by convex SPQ polynomials can be solved by "small" semidefinite programs. Finally, we present applications of SPQ polynomials to bounding the sparsity of solutions of linear programs, polynomial regression problems in statistics, and a generalization of Newton's method which incorporates separable higher-order derivative information.
In this work, we introduce and study the notion of sos-perfectness. For a graph G, we define a quartic homogeneous polynomial pG(x) based on the adjacency relation in G and show that pG(x) is nonnegative for every graph G. A graph G is perfect if for every induced subgraph H of G, the chromatic number of H equals the clique number of H. We say that a graph G is sos-perfect if pH(x) is sum of squares (sos) for every induced subgraph H of G. We show that a graph is perfect if and only if it is sos-perfect. This equivalence together with the strong perfect graph theorem allows us to explicitly provide an infinite family of nonnegative polynomials that are not sos.
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.
We investigate the evolution of the Q values for the implementation of Deep Q Learning (DQL) in the Stable Baselines library. Stable Baselines incorporates the latest Reinforcement Learning techniques and achieves superhuman performance in many game environments. However, for some simple non-game environments, the DQL in Stable Baselines can struggle to find the correct actions. In this paper we aim to understand the types of environment where this suboptimal behavior can happen, and also investigate the corresponding evolution of the Q values for individual states. We compare a smart TrafficLight environment (where performance is poor) with the AI Gym FrozenLake environment (where performance is perfect). We observe that DQL struggles with TrafficLight because actions are reversible and hence the Q values in a given state are closer than in FrozenLake. We then investigate the evolution of the Q values using a recent decomposition technique of Achiam et al.. We observe that for TrafficLight, the function approximation error and the complex relationships between the states lead to a situation where some Q values meander far from optimal.
A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.
A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.
We determine the maximum number of edges that a claw-free graph can have, when its maximum degree and matching number are bounded. This is a famous problem that has been studied on general graphs, and for which there is a tight bound. The graphs achieving this bound contain in most cases an induced copy of K1,3, the claw, which motivates studying the question on claw-free graphs. Note that on general graphs, if one of the mentioned parameters is not bounded, then there is no upper bound on the number of edges. We show that on claw-free graphs, bounding the matching number is sufficient for obtaining an upper bound on the number of edges. The same is not true for the degree, as a long path is claw-free. We give exact tight formulas for both when only the matching number is bounded and when both parameters are bounded. We also construct claw-free graphs whose edge numbers match the given bounds.
A graph G of even order is ℓ-extendable if it is of order at least 2ℓ + 2, contains a matching of size ℓ, and if every such matching is contained in a perfect matching of G. In this paper, we study the extendability of lexicographic products of graphs. We characterize graphs G and H such that their lexicographic product is not 1-extendable. We also provide several conditions on the graphs G and H under which their lexicographic product is 2-extendable.
A graph is equimatchable if all of its maximal matchings have the same size. Equimatchable graphs are extensively studied in the literature mainly from structural point of view. Here we provide the first family of forbidden subgraphs of equimatchable graphs. Since equimatchable graphs are by definition not hereditary, this task of finding forbidden subgraphs requires the use of structural results from previous works.