Search

We consider weighted blocking problems (a.k.a. weighted transversal problems) of the following form. Given a finite set S , weights w : S → R + , and a family F ⊆ 2 S , find min { w ( H ) : H ⊆ S , H intersects every member of F } . In our problems S is the set of edges of a (directed or undirected) graph and F is the family of optimal solutions of a combinatorial optimization problem with respect to a cost function c : S → R + . Note that the cost function c that defines the family and the weight function w in the weighted transversal problem are not related. In particular, we study the following five kinds of families: minimum cost k -spanning trees (unions of k edge-disjoint spanning trees), minimum cost s -rooted k -arborescences (unions of k arc-disjoint arborescences rooted at node s ), minimum cost (directed or undirected) k -braids between nodes s and t (unions of k edge-disjoint s - t paths), and minimum cost (directed or undirected) k -edge-connected subgraphs. We focus on the special cases when either c or w is uniform. For the case c ≡ 0 (i.e. we want to block all combinatorial objects, not just the optimal ones), we show that most of the problems are NP-complete. In the other case, when w ≡ 1 (a minimum cardinality transversal problem for F ), most of our problems turn out to be polynomial-time solvable. [ABSTRACT FROM AUTHOR]

The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet, 1972), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441-448, 2007) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is $$\mathsf {NP}$$ -hard. We also prove $$\mathsf {NP}$$ -hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes. [ABSTRACT FROM AUTHOR]

The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph $$D=(V,A)$$ with a designated root node $$r\in V$$ and arc-costs $$c:A\rightarrow \mathbb {R}$$ , find a minimum cardinality subset H of the arc set A such that H intersects every minimum c-cost r-arborescence. By an r-arborescence we mean a spanning arborescence of root r. The algorithm we give solves a weighted version as well, in which a nonnegative weight function $$w:A\rightarrow \mathbb {R}_+$$ (unrelated to c) is also given, and we want to find a subset H of the arc set such that H intersects every minimum c-cost r-arborescence, and $$w(H)=\sum _{a\in H}w(a)$$ is minimum. The running time of the algorithm is $$O(n^3T(n,m))$$ , where n and m denote the number of nodes and arcs of the input digraph, and T( n, m) is the time needed for a minimum $$s-t$$ cut computation in this digraph. A polyhedral description is not given, and seems rather challenging. [ABSTRACT FROM AUTHOR]

We are given a symmetric crossing supermodular set function p on V and a partition P of V. We solve the problem of finding a graph with vertex set V having edges only between the classes of P such that for every subset X of V the cut of the graph defined by X contains at least p(X) edges. The objective is to minimize the number of edges of the graph. This problem is a common generalization of the global edge-connectivity augmentation of a graph with partition constraints, which was solved by Bang-Jensen et al. [SIAM J. Discrete Math., 12 (1999), pp. 160-207] and the problem of covering a symmetric crossing supermodular set function solved by Benczúr and Frank [Math. Program., 84 (1999), pp. 483-503]. Our problem can be considered as an abstract form of the problem of global edge-connectivity augmentation of a hypergraph with partition constraints, which was earlier solved by the authors [J. Graph Theory, 72 (2013), pp. 291-312]. [ABSTRACT FROM AUTHOR]

We consider the following network design problem that we call the Generalized Terminal Backup Problem: given a graph (or a hypergraph) G0 = (V,E0), a set of (at least 2) terminals T⊆V, and a requirement r(t) for every t ∈ T, find a multigraph G = (V, E) such that λG0+G (t, T - t) ≥ r(t) for any t ∈ T. In the minimum cost version the objective is to find G minimizing the total cost c(E) = Σuv∈Ec(uv), given also costs c(uv) ≥ 0 for every pair u,v ∈ V. In the degree-specified version the question is to decide whether such a G exists, satisfying that the degree of v ∈ V is a prescribed value m(v). The Terminal Backup Problem solved in [E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678-708] is the special case where G0 is the empty graph and r(t) = 1 for every terminal t ∈ T. We solve the Generalized Terminal Backup Problem in the following two cases. In the first case we solve the degree-specified version by a splitting-off theorem. This splitting-off theorem in turn provides the solution for the minimum cost version in the case when c is node-induced, that is c(uv) = w(u) + w(v) for some node weights w : V → ℝ+. In the second case we turn to the general minimum cost version, and we are able to solve it when G0 is the empty graph. This includes the Terminal Backup Problem (r ≡ 1) and the Maximum-Weight b-matching Problem (T = V). The solution depends on an interesting new variant of a theorem of Lovâsz and Cherkassky, and on the solution of the so-called Simplex Matching Problem. Our algorithms run in polynomial time for both problems. [ABSTRACT FROM AUTHOR]

In this paper we fix 7 types of undirected graphs: paths, paths with prescribed endvertices, circuits, forests, spanning trees, (not necessarily spanning) trees and cuts. Given an undirected graph G = ( V , E ) and two “object types” A and B chosen from the alternatives above, we consider the following questions. Packing problem: can we find an object of type A and one of type B in the edge set E of G , so that they are edge-disjoint? Partitioning problem: can we partition E into an object of type A and one of type B ? Covering problem: can we cover E with an object of type A , and an object of type B ? This framework includes 44 natural graph theoretic questions. Some of these problems were well-known before, for example covering the edge-set of a graph with two spanning trees, or finding an s - t path P and an s ′ - t ′ path P ′ that are edge-disjoint. However, many others were not, for example can we find an s - t path P ⊆ E and a spanning tree T ⊆ E that are edge-disjoint? Most of these previously unknown problems turned out to be NP-complete, many of them even in planar graphs. This paper determines the status of these 44 problems. For the NP-complete problems we also investigate the planar version, for the polynomial problems we consider the matroidal generalization (wherever this makes sense). [ABSTRACT FROM AUTHOR]

Given a hypergraph, a partition of its vertex set, and a nonnegative integer k, find a minimum number of graph edges to be added between different members of the partition in order to make the hypergraph k-edge-connected. This problem is a common generalization of the following two problems: edge-connectivity augmentation of graphs with partition constraints (J. Bang-Jensen, H. Gabow, T. Jordán, Z. Szigeti, SIAM J Discrete Math 12(2) (1999), 160-207) and edge-connectivity augmentation of hypergraphs by adding graph edges (J. Bang-Jensen, B. Jackson, Math Program 84(3) (1999), 467-481). We give a min-max theorem for this problem, which implies the corresponding results on the above-mentioned problems, and our proof yields a polynomial algorithm to find the desired set of edges. [ABSTRACT FROM AUTHOR]

Let $${\mathcal{F}}$$ be a family of subsets of an n-element set. $${\mathcal{F}}$$ is called (p,q)-chain intersecting if it does not contain chains $$A_1\subsetneq A_2\subsetneq\dots\subsetneq A_p$$ and $$B_1\subsetneq B_2\subsetneq\dots\subsetneq B_q$$ with $$A_p\cap B_q=\emptyset$$ . The maximum size of these families is determined in this paper. Similarly to the p = q = 1 special case (intersecting families) this depends on the notion of r-complementing-chain-pair-free families, where r = p + q − 1. A family $${\mathcal{F}}$$ is called r-complementing-chain-pair-free if there is no chain $${\mathcal{L}} \subseteq {\mathcal{F}}$$ of length r such that the complement of every set in $${\mathcal{L}}$$ also belongs to $${\mathcal{F}}$$ . The maximum size of such families is also determined here and optimal constructions are characterized. [ABSTRACT FROM AUTHOR]