Search

Several min–max relations in graph theory can be expressed in the framework of the Erdős–Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic. [ABSTRACT FROM AUTHOR]

Line graphs constitute a rich and well-studied class of graphs. In this paper, we focus on three different topics related to line graphs of subcubic triangle-free graphs. First, we show that any such graph G has an independent set of size at least 3 | V ( G ) | ∕ 10 , the bound being sharp. As an immediate consequence, we have that any subcubic triangle-free graph G , with n i vertices of degree i , has a matching of size at least 3 n 1 ∕ 20 + 3 n 2 ∕ 10 + 9 n 3 ∕ 20 . Then we provide several approximate min-max theorems relating cycle-transversals and cycle-packings of line graphs of subcubic triangle-free graphs. This enables us to prove Jones’ Conjecture for claw-free graphs with maximum degree 4 . Finally, we concentrate on the computational complexity of Feedback Vertex Set , Hamiltonian Cycle and Hamiltonian Path for subclasses of line graphs of subcubic triangle-free graphs. [ABSTRACT FROM AUTHOR]

The duality between the robust (or equivalently, model independent) hedging of path dependent European options and a martingale optimal transport problem is proved. The financial market is modeled through a risky asset whose price is only assumed to be a continuous function of time. The hedging problem is to construct a minimal super-hedging portfolio that consists of dynamically trading the underlying risky asset and a static position of vanilla options which can be exercised at the given, fixed maturity. The dual is a Monge-Kantorovich type martingale transport problem of maximizing the expected value of the option over all martingale measures that have a given marginal at maturity. In addition to duality, a family of simple, piecewise constant super-replication portfolios that asymptotically achieve the minimal super-replication cost is constructed. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight , we define a metrized polyhedral complex, called the directed tight span , and prove that the dual of the -weighted maximum multiflow problem reduces to a facility location problem on . Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by . By utilizing this duality, we establish the classifications of terminal weights admitting a combinatorial min–max relation (i) for every network and (ii) for every Eulerian network. Our result includes the Lomonosov–Frank theorem for directed free multiflows and Ibaraki–Karzanov–Nagamochi’s directed multiflow locking theorem as special cases. [Copyright &y& Elsevier]

In multiflow maximization problems, there are several combinatorial duality relations, such as the Ford-Fulkerson max-flow min-cut theorem for single commodity flows, Hu's max-biflow min-cut theorem for two-commodity flows, the Lovász-Cherkassky duality theorem for free multiflows, and so on. In this paper, we provide a unified framework for such multiflow combinatorial dualities by using the notion of a folder complex, which is a certain 2-dimensional polyhedral complex introduced by Chepoi. We show that for a nonnegative weight μ on terminal set, the μ-weighted maximum multiflow problem admits a combinatorial duality relation if and only if μ is represented by distances between certain subsets in a folder complex, and we show that the corresponding combinatorial dual problem is a discrete location problem on the graph of the folder complex. This extends a result of Karzanov in the case of metric weights. [ABSTRACT FROM AUTHOR]

Abstract: Given a (possibly infinite) family of oriented stars, an -packing in a digraph D is a collection of vertex disjoint subgraphs of D, each isomorphic to a member of . The -Packing problem asks for the maximum number of vertices, of a host digraph D, that can be covered by an -packing of D. We prove a dichotomy for the decision version of the -packing problem, giving an exact classification of which problems are polynomial time solvable and which are NP-complete. For the polynomial problems, we provide Hall type min-max theorems, including versions for (locally) degree-constrained variants of the problems. An oriented star can be specified by a pair of denoting the number of out- and in-neighbours of the centre vertex. For , we denote by the family of stars such that , and , and . We prove the -Packing problem is polynomial if for some , and NP-complete otherwise. [Copyright &y& Elsevier]

In 1, we have previously observed that, in a chordal graph G, the maximum number of independent r-cliques (i.e., of vertex disjoint subgraphs of G, each isomorphic to K r, with no edges joining any two of the subgraphs) equals the minimum number of cliques of G that meet all the r-cliques of G. When r = 1, this says that chordal graphs have independence number equal to the clique covering number. When r = 2, this is equivalent to a result of Cameron (1989), and it implies a well known forbidden subgraph characterization of split graphs. In this paper we consider a weighted version of the above min-max optimization problem. Given a chordal graph G, with a nonnegative weight for each r-clique in G, we seek a set of independent r-cliques with maximum total weight. We present two algorithms to solve this problem, based on the principle of complementary slackness. The first one operates on a graph derived from G, and is an adaptation of an algorithm of Farber (1982). The second one improves the performance by reducing the number of constraints of the linear programs. Both results produce a min-max relation. When the algorithms are specialized to the situation in which all the r-cliques have the same weight, we simplify the algorithms reported in 1, although these simpler algorithms are not as efficient. As a byproduct, we also obtain new elementary proofs of the above min-max result. [ABSTRACT FROM AUTHOR]

We consider the following generalization of split graphs: A graph is said to be a (k,ℓ)-graph if its vertex set can be partitioned into k independent sets and ℓ cliques. (Split graphs are obtained by setting k=ℓ=1.) Much of the appeal of split graphs is due to the fact that they are chordal, a property not shared by (k,ℓ)-graphs in general. (For instance, being a (k,0)-graph is equivalent to being k-colourable.) However, if we keep the assumption of chordality, nice algorithms and characterization theorems are possible. Indeed, our main result is a forbidden subgraph characterization of chordal (k,ℓ)-graphs. We also give an O(n(m+n)) recognition algorithm for chordal (k,ℓ)-graphs. When k=1, our algorithm runs in time O(m+n).In particular, we obtain a new simple and efficient greedy algorithm for the recognition of split graphs, from which it is easy to derive the well known forbidden subgraph characterization of split graphs. The algorithm and the characterization extend, in a natural way, to the ‘list’ (or ‘pre-colouring extension’) version of the split partition problem—given a graph with some vertices pre-assigned to the independent set, or to the clique, is there a split partition extending this pre-assignment? Another way to think of our main result is the following min–max property of chordal graphs: for each integer r⩾1, the maximum number of independent Kr''s (i.e., of vertex disjoint subgraphs of G, each isomorphic to Kr, with no edges joining two of the subgraphs) equals the minimum number of cliques of G that meet all the Kr''s of G. [Copyright &y& Elsevier]

This paper solves the problem of increasing the edge-connectivity of a bipartite digraph by adding the smallest number of new edges that preserve bipartiteness. A natural application arises when we wish to reinforce a 2-dimensional square grid framework with cables. We actually solve the more general problem of covering a crossing family of sets with the smallest number of directed edges, where each new edge must join the blocks of a given bipartition of the elements. The smallest number of new edges is given by a min-max formula that has six infinite families of exceptional cases. We discuss a problem on network flows whose solution has a similar formula with three infinite families of exceptional cases. We also discuss a problem on arborescences whose solution has five infinite families of exceptions. We give an algorithm that increases the edge-connectivity of a bipartite digraph in the same time as the best-known algorithm for the problem without the bipartite constraint: O( km log n) for unweighted digraphs and O( nm log ( n2/ m)) for weighted digraphs, where n, m and k are the number of vertices and edges of the given graph and the target connectivity, respectively. [ABSTRACT FROM AUTHOR]

A brief review of relativistic quantum chemistry is given here. Relativistic effects and their importance in chemistry are discussed. An outline of different theoretical aspects is presented. Aspects of variation techniques relevant to relativistic calculations are discussed in detail. These involve the derivation of min-max theorems for Dirac, Dirac-Hartree-Fock and Dirac-Coulomb calculations. The consequence of relativistic Hamiltonians being unbounded are also discussed for other lines of investigation. The upper bounds derived are physically interpreted. Sample Dirac-Hartree-Fock results for the Be atom, calculated using both STO and GTO bases for the nonrelativistic orbitals and the upper components of the relativistic orbitals, are given. The inadequacy of the so-called kinetically balanced basis set is discussed and illustrated with these results. The importance of the variational or dynamical balance and hence the merit of the LCAS-MS scheme is pointed out. The possibility of calculating quantum electrodynamical pair energy from relativistic configuration interaction calculations on a two-electron atom is discussed and exemplified. The present status of relativistic molecular calculations is briefly reviewed. Conclusions on the aspects of variational analysis and molecular calculations are enclosed. [ABSTRACT FROM AUTHOR]