Search

Let D be a digraph. A subset S of V(D) is stable if every pair of vertices in S is non-adjacent in D. A collection of disjoint paths P of D is a path partition of V(D), if every vertex in V(D) is on a path of P . We say that a stable set S and a path partition P are orthogonal if every path of P contains exactly one vertex of S. A digraph D satisfies the α -property if for every maximum stable set S of D, there is a path partition P orthogonal to S. A digraph D is α -diperfect if every induced subdigraph of D satisfies the α -property. In 1982, Berge proposed a characterization of α -diperfect digraphs in terms of forbidden anti-directed odd cycles. In 2018, Sambinelli, Silva and Lee proposed a similar conjecture. A digraph D satisfies the Begin–End-property or BE-property if for every maximum stable set S of D, there is a path partition P such that (i) S and P are orthogonal and (ii) for each path P ∈ P , either the initial or the final of P lies in S. A digraph D is BE-diperfect if every induced subdigraph of D satisfies the BE-property. Sambinelli, Silva and Lee proposed a characterization of BE-diperfect digraphs in terms of forbidden blocking odd cycles. In this paper, we show some structural results for α -diperfect and BE-diperfect digraphs. In particular, we show that in every minimal counterexample D to both conjectures, it follows that α (D) < | V (D) | / 2 . Moreover, we prove both conjectures for arc-locally (out) in-semicomplete digraphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider integral (and fractional) packing problems in generalized kernel systems with a mixed family ( gksmf). This framework generalizes combinatorial packing problems of several structures as, for instance, st-flows, arborescences, kernel systems, branchings, convex branchings, and covers in bi-set systems. We provide an algorithm, which improves by a factor of 2 on the upperbound for the size of a packing in a gksmf, provided by Leston-Rey and Wakabayashi. This in turn implies the following upperbounds, where n is the number of vertices, m the number of arcs, and r the number of root-sets of a digraph: m for the size of a packing of st-paths; $$m-n+2$$ for the size of a packing of spanning arborescences; $$m+r-1$$ for the size of a packing of spanning branchings; $$m+r-1$$ for the size of a packing of Fujishige's convex branchings; m for the size of a packing of dijoins of a restricted form; and $$m+r-1$$ for the size of a packing in Frank's bi-set systems with the mixed intersection property. Next, we consider the framework of uncrossing gksmf. We describe an algorithm for computing a packing in such a framework with the same upperbound guarantee. The time complexity of this algorithm implies an improvement over the best time complexity bounds known for computing a packing of spanning arborescences of Gabow and Manu, for computing a packing of spanning branchings of Lee and Leston-Rey, and for computing a packing of covers in a bi-set system with the mixed intersection property of Bérczi and Frank. [ABSTRACT FROM AUTHOR]

We consider the problem of finding an integral (and fractional) packing of branchings in a capacitated digraph with root-set demands. Schrijver described an algorithm that returns a packing with at most m + n 3 + r branchings that makes at most m ( m + n 3 + r ) calls to an oracle that basically computes a minimum cut, where n is the number of vertices, m is the number of arcs and r is the number of root-sets of the input digraph. Leston-Rey and Wakabayashi described an algorithm that returns a packing with at most m + r − 1 branchings but makes a large number of oracle calls. In this work we provide an algorithm, inspired on ideas of Schrijver and in a paper of Gabow and Manu, that returns a packing with at most m + r − 1 branchings and makes at most ( m + r + 2 ) n oracle calls. Moreover, for the arborescence packing problem our algorithm provides a packing with at most m − n + 2 arborescences–thus improving the bound of m of Leston-Rey and Wakabayashi–and makes at most ( m − n + 5 ) n oracle calls. [ABSTRACT FROM AUTHOR]

Background: During evolution, global mutations may alter the order and the orientation of the genes in a genome. Such mutations are referred to as rearrangement events, or simply operations. In unichromosomal genomes, the most common operations are reversals, which are responsible for reversing the order and orientation of a sequence of genes, and transpositions, which are responsible for switching the location of two contiguous portions of a genome. The problem of computing the minimum sequence of operations that transforms one genome into another - which is equivalent to the problem of sorting a permutation into the identity permutation - is a well-studied problem that finds application in comparative genomics. There are a number of works concerning this problem in the literature, but they generally do not take into account the length of the operations (i.e. the number of genes affected by the operations). Since it has been observed that short operations are prevalent in the evolution of some species, algorithms that efficiently solve this problem in the special case of short operations are of interest. Results: In this paper, we investigate the problem of sorting a signed permutation by short operations. More precisely, we study four flavors of this problem: (i) the problem of sorting a signed permutation by reversals of length at most 2; (ii) the problem of sorting a signed permutation by reversals of length at most 3; (iii) the problem of sorting a signed permutation by reversals and transpositions of length at most 2; and (iv) the problem of sorting a signed permutation by reversals and transpositions of length at most 3. We present polynomial-time solutions for problems (i) and (iii), a 5-approximation for problem (ii), and a 3-approximation for problem (iv). Moreover, we show that the expected approximation ratio of the 5-approximation algorithm is not greater than 3 for random signed permutations with more than 12 elements. Finally, we present experimental results that show that the approximation ratios of the approximation algorithms cannot be smaller than 3. In particular, this means that the approximation ratio of the 3-approximation algorithm is tight. [ABSTRACT FROM AUTHOR]

Abstract: We consider the following problem. For every positive integer k there is a smallest integer such that for any two vertices s and t in a non-bipartite -connected graph G, there is an s–t path P in G with specified parity such that is k-connected. This conjecture is a variant of the well-known conjecture of Lovász with the parity condition. Indeed, this conjecture is strictly stronger. Lovász' conjecture is wide open for . In this paper, we show that and . We also consider a conjecture of Thomassen which says that there exists a function such that every -connected graph with an odd cycle contains an odd cycle C such that is k-connected. We show the following strengthening of Thomassen's conjecture for the case . Namely; let G be a 5-connected graph and s be a vertex in G such that is not bipartite. Then there is an odd cycle C avoiding s such that is 2-connected. [Copyright &y& Elsevier]

Abstract: Let be a mixed graph with vertex set , edge set and arc set . A cycle cover of is a family of cycles of such that each edge/arc of belongs to at least one cycle in . The weight of is . The minimum cycle cover problem is the following: given a strongly connected mixed graph without bridges, find a cycle cover of with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph , find a minimum length closed walk using all edges and arcs of . These problems are NP-hard. We show that they can be solved in polynomial time if has bounded tree-width. [Copyright &y& Elsevier]

Abstract: We prove there exists a function such that for every -connected graph G and for every edge , there exists an induced cycle C containing e such that is k-connected. This proves a weakening of a conjecture of Lovász due to Kriesell. [Copyright &y& Elsevier]

Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an O(∣V∣²) algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an O(∣V∣³) algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs. [ABSTRACT FROM AUTHOR]

In this paper we give a decomposition of a 4-connected graph G into nonseparating chains, which is similar to an ear decomposition of a 2-connected graph. We also give an O(∣V (G)∣2∣E(G)∣) algorithm that constructs such a decomposition. In applications, the asymptotic performance can often be improved to O(∣V (G)∣3). This decomposition will be used to find four independent spanning trees in a 4-connected graph. [ABSTRACT FROM AUTHOR]

In this paper, we describe an O (|V (G)|| E (G)|) algorithm for finding a nonseparating planar chain in a 4-connected graph G, which will be used to decompose an arbitrary 4-connected graph into planar chains. This work was motivated by the study of a multitree approach to reliability in distributed networks, as well as the study of nonseparating induced paths in highly connected graphs. [ABSTRACT FROM AUTHOR]

In 1975, Lovász conjectured that for any positive integerk, there exists a minimum positive integerf(k) such that, for any two verticesx,yin anyf(k)-connected graphG, there is a pathPfromxtoyinGsuch thatG-V(P) isk-connected. A result of Tutte impliesf(1) = 3. Recently,f(2) = 5 was shown by Chenet al. and, independently, by Kriesell. In this paper, we show thatf(2) = 4 except for double wheels. [ABSTRACT FROM AUTHOR]

The number Z (n) : = ⌊ n / 2 ⌋ ⌊ (n - 1) / 2 ⌋ is the smallest number of crossings in a simple planar drawing of K 2 , n in which both vertices on the 2-side have the same clockwise rotation. For two vertices u, v on the q-side of a simple drawing of K p , q , let cr D (u , v) denote the total number of crossings that edges incident with u have with edges incident with v. We show that in any simple drawing D of K p , q in a surface Σ the number of pairs of vertices on the q-side of K p , q having cr D (u , v) < Z (p) is bounded as a function of p and Σ . As a consequence, we also show that, for a fixed integer p and surface Σ , there exists a finite set of drawings D (p , Σ) of complete bipartite graphs such that, for each q, a crossing-minimal drawing of K p , q can be obtained by "duplicating vertices" in some drawing from D (p , Σ) . [ABSTRACT FROM AUTHOR]

In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS'05), in which we are given a demand r t ∈ { 0 , 1 } for instant of time t = 0 , ... , T − 1 , along with K permit types with lengths of time δ 1 , ... , δ K and sub-additive costs. A permit is a pair (k , t ˆ) ∈ K × Z + , and it covers interval t ˆ , t ˆ + δ k). We wish to find a minimum-cost set of permits that covers every t with r t = 1. Meyerson gave deterministic O (K) -competitive and randomized O (lg K) -competitive online algorithms for this problem, as well as matching lower bounds. The first variant we propose is the multi parking permit problem, in which an arbitrary demand is given at each instant ( r t ∈ Z + ) and we may buy multiple permits to serve it. We prove that the offline version of this problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields a deterministic O (K) -competitive online algorithm and a randomized O (lg K) -competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O (lg n) -approximation algorithm and a O (lg K lg | V |) -competitive online algorithm, where n is the number of requests and | V | is the size of the input metric. The second variant we propose is the group parking permit problem, in which we also have an arbitrary demand for each instant, and each permit of type k can be either a single permit, costing γ k and covering one demand per instant of time, or a group permit, which costs M ⋅ γ k for some constant M ≥ 1 and covers an arbitrary number of demands in the interval covered by this permit. (I.e., group permits have infinite capacity.) For this version of the problem, we give an 8-approximation algorithm and a deterministic O (K) -competitive online algorithm. The first result yields an improvement on the previous best approximation algorithm for the leasing version of the rent-or-buy problem. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid (2015), in which a permit type is defined by a length of time and an integer capacity. They presented a constant approximation algorithm and a deterministic O (K) -competitive online algorithm for a hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time algorithms. Moreover, these results yield approximation and competitive online algorithms for a hierarchical leasing version of the buy-at-bulk network design problem. We also show that their original pseudo-polynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NP-hard. [ABSTRACT FROM AUTHOR]

Let D be a digraph. A stable set S of D and a path partition P of D are orthogonal if every path P ∈ P contains exactly one vertex of S. In 1982, Berge defined the class of α -diperfect digraphs. A digraph D is α-diperfect if for every maximum stable set S of D there is a path partition P of D orthogonal to S and this property holds for every induced subdigraph of D. An anti-directed odd cycle is an orientation of an odd cycle (x 0 , ... , x 2 k , x 0) with k ≥ 2 in which each vertex x 0 , x 1 , x 2 , x 3 , x 5 , x 7 , ... , x 2 k − 1 is either a source or a sink. Berge conjectured that a digraph D is α -diperfect if and only if D does not contain an anti-directed odd cycle as an induced subdigraph. In this paper, we show that this conjecture is false by exhibiting an infinite family of orientations of complements of odd cycles with at least seven vertices that are not α -diperfect. [ABSTRACT FROM AUTHOR]

A path partition P of a digraph D is a set of disjoint paths which covers V ( D ) . Let k be a positive integer. The k -norm of a path partition P of a digraph is defined as ∑ P ∈ P min { | V ( P ) | , k } . Let π k ( D ) denote the smallest k -norm among all path partitions of a digraph D . In 1981, Linial conjectured that for any positive integer k each digraph D contains k disjoint stable sets whose union has size at least π k ( D ) . We prove this conjecture for a class of digraphs we call spine digraphs, which is a proper generalization of split digraphs. [ABSTRACT FROM AUTHOR]

The Connected Facility Location (CFL) is a network design problem that arises from a combination of the Uncapacitated Facility Location (FL) and the Steiner Tree (ST) problems. The Online Connected Facility Location problem (OCFL) is an online version of the CFL. San Felice et al. (2014) presented a randomized algorithm for the OCFL and proved that it is $$\mathrm {O}(\log ^2 n)$$ -competitive, where n is the number of clients. That algorithm combines the sample-and-augment framework of Gupta, Kumar, Pál, and Roughgarden with previous algorithms for the Online Facility Location (OFL) and the Online Steiner Tree (OST) problems. In this paper we use a more precise analysis to show that the same algorithm is $$\mathrm {O}(\log n)$$ -competitive. Since there is a lower bound of $$\mathrm {\Omega }(\log n)$$ for this problem, our result achieves the best possible competitive ratio, asymptotically. [ABSTRACT FROM AUTHOR]

We consider questions related to the existence of spanning trees in connected graphs with the property that, after the removal of any path in the tree, the graph remains connected. We show that, for planar graphs, the existence of trees with this property is closely related to the Hamiltonicity of the graph. For graphs with a 1- or 2-vertex cut, the Hamiltonicity also plays a central role. We also deal with spanning trees satisfying this property restricted to paths arising from fundamental cycles. The cycle space of a graph can be generated by the fundamental cycles of every spanning tree, and Tutte showed that, for a 3-connected graph, it can be generated by nonseparating cycles. We are also interested in the existence of a fundamental basis consisting of nonseparating cycles. [ABSTRACT FROM AUTHOR]

Let D be a digraph. A coloring C and a path P of D are orthogonal if P contains exactly one vertex of each color class in C. In 1982, Berge defined the class of χ -diperfect digraphs. A digraph D is χ -diperfect if for every minimum coloring C of D , there exists a path P orthogonal to C and this property holds for every induced subdigraph of D. Berge showed that every symmetric digraph is χ -diperfect, as well as every digraph whose underlying graph is perfect. However, he also showed that not every super-orientation of an odd cycle or complement of an odd cycle is χ -diperfect. Non- χ -diperfect super-orientations of odd cycles and their complements may play an important role in the characterization of χ -diperfect digraphs, similarly to the role they play in the characterization of perfect graphs. In this paper, we present a characterization of super-orientations of odd cycles and a characterization of super-orientations of complements of odd cycles that are χ -diperfect. Moreover, we show that certain classes of digraphs that are free of such non- χ -diperfect structures are χ -diperfect. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we prove the following result. Suppose that s and t are vertices of a 3-connected graph G such that is not bipartite and there is no cutset X of size three in G for which some component U of is disjoint from . Then either (1) G contains an induced path P from s to t such that is not bipartite or (2) G can be embedded in the plane so that every odd face contains one of s or t. Furthermore, if (1) holds then we can insist that is connected, while if G is 5-connected then (1) must hold and P can be chosen so that is 2-connected. [Copyright &y& Elsevier]

A path decomposition of a graph G is a set of edge‐disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph with n vertices admits a path decomposition of size at most ⌊(n+1)∕2⌋. Gallai's conjecture was verified for many classes of graphs. In particular, Lovász (1968) verified this conjecture for graphs with at most one vertex of even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex of odd degree. Recently, Bonamy and Perrett verified Gallai's conjecture for graphs with maximum degree at most 5. In this paper, we verify Gallai's conjecture for graphs with treewidth at most 3. Moreover, we show that the only graphs with treewidth at most 3 that do not admit a path decomposition of size at most ⌊n∕2⌋ are isomorphic to K3 or K5−, the graph obtained from K5 by removing an edge. [ABSTRACT FROM AUTHOR]

The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one. [ABSTRACT FROM AUTHOR]

Let k be a positive integer and let D be a digraph. A path partition P of D is a set of vertex-disjoint paths which covers V(D). Its k-norm is defined as ∑ P ∈ P min { | V (P) | , k } . A path partition is k-optimal if its k-norm is minimum among all path partitions of D. A partialk-coloring is a collection of k disjoint stable sets. A partial k-coloring C is orthogonal to a path partition P if each path P ∈ P meets min { | V (P) | , k } distinct sets of C . Berge (Eur J Comb 3(2):97–101, 1982) conjectured that every k-optimal path partition of D has a partial k-coloring orthogonal to it. A (path) k-pack of D is a collection of at most k vertex-disjoint paths in D. Its weight is the number of vertices it covers. A k-pack is optimal if its weight is maximum among all k-packs of D. A coloring of D is a partition of V(D) into stable sets. A k-pack P is orthogonal to a coloring C if each set C ∈ C meets min { | C | , k } paths of P . Aharoni et al. (Pac J Math 2(118):249–259, 1985) conjectured that every optimal k-pack of D has a coloring orthogonal to it. A digraph D is semicomplete if every pair of distinct vertices of D are adjacent. A digraph D is locally in-semicomplete if, for every vertex v ∈ V (D) , the in-neighborhood of v induces a semicomplete digraph. Locally out-semicomplete digraphs are defined similarly. In this paper, we prove Berge's and Aharoni–Hartman–Hoffman's Conjectures for locally in/out-semicomplete digraphs. [ABSTRACT FROM AUTHOR]