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.
Nonnegativity of a polynomial does not generally imply that it can be written as a sum of squares of polynomials, except in a few cases, such as the polynomial being separable or it being quadratic. Here we study polynomials that are sums of separable and quadratic terms. We show that being nonnegative and being sum of squares are not equivalent for polynomials of this structure. In fact, we show that the equivalence only holds true for the same cases as those for which nonnegative polynomials are sum of squares. We then show that deciding nonnegativity of polynomials of this structure is NP-hard, whereas deciding convexity amounts to solving a single semidefinite program. We also show that convex polynomials of this structure are nonnegative if and only if they are sum of squares, a property that is not true for general convex polynomials. Finally, we present possible application areas where sums of separable and quadratic polynomials appear and perform some numerical experiments.
In this work, we introduce and study the notion of sos-perfectness. For a graph G, we define a certain 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. 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.