Skew-representable matroids form a fundamental class in matroid theory, bridging combinatorics and linear algebra. They play an important role in areas such as coding theory, optimization, and combinatorial geometry, where linear structure is crucial for both theoretical insights and algorithmic applications. Since deciding skew-representability is computationally intractable, much effort has been focused on identifying necessary or sufficient conditions for a matroid to be skew-representable.

Abstract. Submodular set functions are undoubtedly among the most important building blocks of combinatorial optimization. Somewhat surprisingly, continuous counterparts of such functions have also appeared in an analytic line of research where they found applications in the theory of finitely additive measures, nonlinear integrals, and electric capacities. Recently, a number of connections between these two branches have been established, and the aim of this paper is to generalize further results on submodular set functions on finite sets to the analytic setting. We first extend the notion of duality of matroids to submodular set functions and characterize the uniquely determined decomposition of a submodular set function into the sum of a nonnegative charge and an increasing submodular set function in which the charge is maximal. Then, we describe basic properties of infinite-alternating set functions, a subclass of submodular set functions that serves as an analytic counterpart of coverage functions. By relaxing the monotonicity assumption in the definition, we introduce a new class of submodular functions with distinguished structural properties that includes, among others, weighted cut functions of graphs. We prove that, unlike general submodular set functions over an infinite domain, any infinite-alternating set function can be written as the sum of an increasing and a decreasing submodular function or as the difference of two increasing submodular functions, thus giving an extension of results on monotonic decompositions in the finite case. Finally, motivated by its connections to graph parameters such as the maximum size of a cut and the maximum size of a fractional triangle packing, we study the structure of such decompositions for weighted cut functions of undirected graphs.

The submodular partitioning problem asks to minimize, over all partitions P of a ground set V , the sum of a given submodular function f over the parts of P . The problem has seen considerable work in approximability, as it encompasses multiterminal cuts on graphs, k -cuts on hypergraphs, and elementary linear algebra problems such as matrix multiway partitioning. This research has been divided between the fixed terminal setting, where we are given a set of terminals that must be separated by P , and the global setting, where the only constraint is the size of the partition. We investigate a generalization that unifies these two settings: minimum submodular matroid-constrained partition. In this problem, we are additionally given a matroid over the ground set and seek to find a partition P in which there exists some basis that is separated by P . We explore the approximability of this problem and its variants for general, symmetric, and monotone submodular functions.

The study of matroid products traces back to the 1970s, when Lovász and Mason studied the existence of various types of matroid products with different strengths. Among these, the tensor product is arguably the most important, which can be considered as an extension of the tensor product from linear algebra. However, Las Vergnas showed that the tensor product of two matroids does not always exist. Over the following four decades, matroid products remained surprisingly underexplored, regaining attention only in recent years due to applications in tropical geometry, information theory, and the limit theory of matroids. In this paper, inspired by the concept of coupling in probability theory, we introduce the notion of coupling for matroids – or, more generally, for submodular set functions. This operation can be viewed as a relaxation of the tensor product. Unlike the tensor product, however, we prove that a coupling always exists for any two submodular functions and can be chosen to be increasing if the original functions are increasing. As a corollary, we show that two matroids always admit a matroid coupling, leading to a novel operation on matroids. Our construction is algorithmic, providing an oracle for the coupling matroid through a polynomial number of oracle calls to the original matroids. We apply this construction to derive new necessary conditions for matroid representability and establish connection between tensor products and Ingleton’s inequality. In addition, we verify the existence of set functions that are universal with respect to a given property, meaning any set function over a finite domain with that property can be obtained as a quotient.

Bérczi K., Király T., Kobayashi Y., et al. Finding spanning trees with perfect matchings. Discrete Applied Mathematics 371, 137 (2025); https://doi.org/10.1016/j.dam.2025.04.001.

In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree. The problem is interesting not only from a graph coloring point of view, but is also closely related to the Degree Bounded Spanning Tree and (1,2)-Traveling Salesman problems. We propose an optimization version called Maximum-size Properly Colored Forest problem, which aims to find a properly colored forest with as many edges as possible. We consider the problem in different graph classes and for different numbers of colors, and present polynomial-time approximation algorithms as well as inapproximability results for these settings. We also consider the Maximum-size Properly Colored Tree problem asking for the maximum size of a properly colored tree not necessarily spanning all the vertices. We show that the optimum is significantly more difficult to approximate than in the forest case, and provide an approximation algorithm for complete multigraphs.

The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of that vertex while preserving their degrees. Lovász [Lov{á}sz, 1974; Lov{á}sz, 1993] and Mader [Mader, 1978] showed the existence of this operation while preserving global and local connectivities respectively in graphs under certain conditions. These results have far-reaching applications in graph algorithms literature [Lovász, 1976; Mader, 1978; Frank, 1993; Frank and Király, 2002; Király and Lau, 2008; Frank, 1992; Goemans and Bertsimas, 1993; Frank, 1994; Bang-Jensen et al., 1995; Frank, 2011; Nagamochi and Ibaraki, 2008; Nagamochi et al., 1997; Henzinger and Williamson, 1996; Goemans, 2001; Jordán, 2003; Kriesell, 2003; Jain et al., 2003; Chan et al., 2011; Bhalgat et al., 2008; Lau, 2007; Chekuri and Shepherd, 2008; Nägele and Zenklusen, 2020; Blauth and Nägele, 2023]. In this work, we introduce a splitting-off operation in hypergraphs. We show that there exists a local connectivity preserving complete splitting-off in hypergraphs and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs. We illustrate the usefulness of our splitting-off operation in hypergraphs by showing two applications: (1) we give a constructive characterization of k-hyperedge-connected hypergraphs and (2) we give an alternate proof of an approximate min-max relation for max Steiner rooted-connected orientation of graphs and hypergraphs (due to Király and Lau [Király and Lau, 2008]). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams' strong orientation theorem and uses tools developed for hypergraphs.

In recent years, combinatorial reconfiguration problems have attracted great attention due to their connection to various topics such as optimization, counting, enumeration, or sampling. One of the most intriguing open questions concerns the exchange distance of two matroid basis sequences, a problem that appears in several areas of computer science and mathematics. In 1980, White proposed a conjecture for the characterization of two basis sequences being reachable from each other by symmetric exchanges, which received a significant interest also in algebra due to its connection to toric ideals and Gr'obner bases. In this work, we verify White’s conjecture for basis sequences of length two in regular matroids, a problem that was formulated as a separate question by Farber, Richter, and Shank and Andres, Hochst'attler, and Merkel. Most of previous work on White’s conjecture has not considered the question from an algorithmic perspective. We study the problem from an optimization point of view: our proof implies a polynomial algorithm for determining a sequence of symmetric exchanges that transforms a basis pair into another, thus providing the first polynomial upper bound on the exchange distance of basis pairs in regular matroids. As a byproduct, we verify a conjecture of Gabow from 1976 on the serial symmetric exchange property of matroids for the regular case.

Two pairs of disjoint bases P1=(R1,B1) and P2=(R2,B2) of a matroid M are called equivalent if P1 can be transformed into P2 by a series of symmetric exchanges. In 1980, White conjectured that such a sequence always exists whenever R1∪B1=R2∪B2. A strengthening of the conjecture was proposed by Hamidoune, stating that the minimum length of an exchange is at most the rank of the matroid. We propose a weighted variant of Hamidoune’s conjecture, where the weight of an exchange depends on the weights of the exchanged elements. We prove the conjecture for several matroid classes: strongly base orderable matroids, split matroids, graphic matroids of wheels, and spikes.

Abstract. Horn functions form a subclass of Boolean functions possessing interesting structural and computational properties. These functions play a fundamental role in algebra, artificial intelligence, combinatorics, computer science, database theory, and logic. In the present paper, we introduce the subclass of hypergraph Horn functions that generalizes matroids and equivalence relations. We provide multiple characterizations of hypergraph Horn functions in terms of implicate-duality and the closure operator, which are, respectively, regarded as generalizations of matroid duality and the Mac Lane–Steinitz exchange property of matroid closure. We also study algorithmic issues on hypergraph Horn functions and show that the recognition problem (i.e., deciding if a given definite Horn CNF represents a hypergraph Horn function) and key realization (i.e., deciding if a given hypergraph is realized as a key set by a hypergraph Horn function) can be done in polynomial time, while implicate sets can be generated with polynomial delay.

Abstract. The basis exchange axiom has been a driving force in the development of matroid theory. However, the axiom gives only a local characterization of the relation of bases, which is a major stumbling block to further progress, and providing a global understanding of the structure of matroid bases is a fundamental goal in matroid optimization. While studying the structure of symmetric exchanges, Gabow proposed the problem that any pair of bases admits a sequence of symmetric exchanges. A different extension of the exchange axiom was proposed by White, who investigated the equivalence of compatible basis sequences. These conjectures suggest that the family of bases of a matroid possesses much stronger structural properties than we are aware of. In the present paper, we study the distance of basis pairs of a matroid in terms of symmetric exchanges. In particular, we give a polynomial-time algorithm that determines a shortest possible exchange sequence that transforms a basis pair into another for split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. As a corollary, we verify the above-mentioned long-standing conjectures for this large class. As paving matroids form a subclass of split matroids, our result settles the conjectures for paving matroids as well.

In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we give a pseudo-polynomial time algorithm that always finds an EFX allocation of chores. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are {0,+1}-valued functions, and negative Boolean utilities that are {0,−1}-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.

We introduce a new class of inverse optimization problems in which an input solution is given together with k linear weight functions, and the goal is to modify the weights by the same deviation vector p so that the input solution becomes optimal with respect to each of them, while minimizing ‖p‖1. In particular, we concentrate on three problems with multiple weight functions: the inverse shortest s−t path, the inverse bipartite perfect matching, and the inverse arborescence problems. Using LP duality, we give min–max characterizations for the ℓ1-norm of an optimal deviation vector. Furthermore, we show that the optimal p is not necessarily integral even when the weight functions are so, therefore computing an optimal solution is significantly more difficult than for the single-weighted case. We also give a necessary and sufficient condition for the existence of an optimal deviation vector that changes the values only on the elements of the input solution, thus giving a unified understanding of previous results on arborescences and matchings.

Abstract. Dynamic pricing schemes were introduced as an alternative to posted-price mechanisms. In contrast to static models, the dynamic setting allows us to update the prices between buyer-arrivals based on the remaining sets of items and buyers, and so it is capable of maximizing social welfare without the need for a central coordinator. In this paper, we study the existence of optimal dynamic pricing schemes in combinatorial markets. In particular, we concentrate on multidemand valuations, a natural extension of unit-demand valuations. The proposed approach is based on computing an optimal dual solution of the maximum social welfare problem with distinguished structural properties. Our contribution is twofold. By relying on an optimal dual solution, we show the existence of optimal dynamic prices in unit-demand markets and in multidemand markets up to three buyers, thus giving new interpretations of results of Cohen-Addad et al. [ Proceedings of the ACM Conference on Economics and Computation, 2016, pp. 383–400] and Berger, Eden, and Feldman [ Proceedings of the International Conference on Web and Internet Economics, Springer, 2020, pp. 206–219], respectively. Furthermore, we provide an optimal dynamic pricing scheme for bidemand valuations with an arbitrary number of buyers. In all cases, our proofs also provide efficient algorithms for determining the optimal dynamic prices.

Abstract. Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds’ fundamental theorem provides a min-max characterization for the unweighted setting, while Frank’s weight-splitting theorem provides one for the weighted case. Several efficient algorithms were developed for these problems, all relying on the usage of one of the conventional oracles for both matroids. In the present paper, we consider the tractability of the matroid intersection problem under restricted oracles. In particular, we focus on the rank sum, common independence, and maximum rank oracles. We give a strongly polynomial-time algorithm for weighted matroid intersection under the rank sum oracle. In the common independence oracle model, we prove that the unweighted matroid intersection problem is tractable when one of the matroids is a partition matroid and that even the weighted case is solvable when one of the matroids is an elementary split matroid. Finally, we show that the common independence and maximum rank oracles together are strong enough to realize the steps of our algorithm under the rank sum oracle.

Horn functions form an important subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem admitting a $2^{\log^{1-o(1)}n}$ inapproximability bound. In this paper we consider the natural class of key Horn functions representing keys of relational databases. For this class, the minimization problems for most measures remain NP-hard. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all such measures.

In the Many-visits Path TSP, we are given a set of $n$ cities along with their pairwise distances (or costs) $c(uv)$, and moreover each city $v$ comes with an associated positive integer request $r(v)$. The goal is to find a minimum-cost path, starting at city $s$ and ending at city $t$, that visits each city $v$ exactly $r(v)$ times. We present a $3/2$-approximation algorithm for the metric Many-visits Path TSP that runs in time polynomial in $n$ and polylogarithmic in the requests $r(v)$. Our algorithm can be seen as a generalization of the $3/2$-approximation algorithm for Path TSP by Zenklusen [ Proceedings of SODA, 2019, pp. 1539--1549], which answered a long-standing open problem by providing an efficient algorithm which matches the approximation guarantee of Christofides' algorithm from 1976 for metric TSP. One of the key components of our approach is a polynomial-time algorithm to compute a connected, degree-bounded multigraph of minimum cost in an undirected graph with edge costs. We tackle this problem by generalizing a fundamental result of Király, Lau, and Singh [ Combinatorica, 32 (2012), pp. 705--720] on the Minimum Bounded Degree Matroid Basis problem, and devise such an algorithm for generalized polymatroids, even allowing element multiplicities. Our result directly yields a $3/2$-approximation to the metric Many-visits TSP, as well as a $3/2$-approximation for the problem of scheduling classes of jobs with sequence-dependent setup times on a single machine so as to minimize the makespan.

Given a relational database, a key is a set of attributes such that a value assignment to this set uniquely determines the values of all other attributes. The database uniquely defines a pure Horn function h, representing the functional dependencies. If the knowledge of the attribute values in set A determines the value for attribute v, then A→v is an implicate of h. If K is a key of the database, then K→v is an implicate of h for all attributes v. Keys of small sizes play a crucial role in various problems. We present structural and complexity results on the set of minimal keys of pure Horn functions. We characterize Sperner hypergraphs for which there is a unique pure Horn function with the given hypergraph as the set of minimal keys. Furthermore, we show that recognizing such hypergraphs is co-NP-complete already when every hyperedge has size two. On the positive side, we identify several classes of graphs for which the recognition problem can be decided in polynomial time. We also present an algorithm that generates the minimal keys of a pure Horn function with polynomial delay, improving on earlier results. By establishing a connection between keys and target sets, our approach can be used to generate all minimal target sets with polynomial delay when the thresholds are bounded by a constant. As a byproduct, our proof shows that the Minimum Key problem is at least as hard as the Minimum Target Set Selection problem with bounded thresholds.

In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable of achieving optimal social welfare without a central tie-breaking coordinator. In the case of two buyers with matroid rank valuations, we give polynomial-time algorithms that always find such prices when one of the matroids is a partition matroid or both matroids are strongly base orderable. This result partially answers a question raised by Dütting and Végh [Private communication, 2017]. We further formalize a weighted variant of the conjecture of Dütting and Végh, and show that the weighted variant can be reduced to the unweighted one based on the weight-splitting theorem for weighted matroid intersection by Frank. We also show that a similar reduction technique works for M${}^\natural$-concave functions or, equivalently, for gross substitutes functions.

In the list coloring problem for two matroids, we are given matroids $M_1=(S,{\mathcal{I}}_1)$ and $M_2=(S,{\mathcal{I}}_2)$ on the same ground set $S$, and the goal is to determine the smallest number $k$ such that, given arbitrary lists $L_s$ of $k$ colors for $s\in S$, it is possible to choose a color from each list so that every monochromatic set is independent in both $M_1$ and $M_2$. When both $M_1$ and $M_2$ are partition matroids, Galvin's celebrated list coloring theorem for bipartite graphs gives the answer. However, not much is known about the general case. One of the main open questions is to decide if there exists a constant $c$ such that if the coloring number is $k$ (i.e., the ground set can be partitioned into $k$ common independent sets), then the list coloring number is at most $c\cdot k$. In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, specifically graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much and might be of independent combinatorial interest. In particular, we show that if $M=(S,{\mathcal{I}})$ is a matroid in which $S$ can be partitioned into $k$ independent sets, then there exists a partition matroid $N=(S,{\mathcal{J}})$ with ${\mathcal{J}}\subseteq{\mathcal{I}}$ in which $S$ can be partitioned into (A) $k$ independent sets if $M$ is a transversal matroid, (B) $2k-1$ independent sets if $M$ is a graphic matroid, (C) $\lceil kr/(r-1)\rceil$ independent sets if $M$ is a paving matroid of rank $r$, and (D) $2k-2$ independent sets if $M$ is a gammoid. It should be emphasized that in cases (A), (B), and (D) the rank of $N$ is the same as that of $M$. We further extend our results to a much broader family by showing that taking direct sum, homomorphic image, or truncation of matroids from these classes results in a matroid admitting a reduction to a partition matroid with coloring number at most twice the original one.

Given a CNF formula Φ with clauses C1,…,Cm and variables V={x1,…,xn}, a truth assignment a:V→{0,1} of Φ leads to a clause sequence σΦ(a)=(C1(a),…,Cm(a))∈{0,1}m where Ci(a)=1 if clause Ci evaluates to 1 under assignment a, otherwise Ci(a)=0. The set of all possible clause sequences carries a lot of information on the formula, e.g. SAT, MAX-SAT and MIN-SAT can be encoded in terms of finding a clause sequence with extremal properties. We consider a problem posed at Dagstuhl Seminar 19211 “Enumeration in Data Management” (2019) about the generation of all possible clause sequences of a given CNF with bounded dimension. We prove that the problem can be solved in incremental polynomial time. We further give an algorithm with polynomial delay for the class of tractable CNF formulas. We also consider the generation of maximal and minimal clause sequences, and show that generating maximal clause sequences is NP-hard, while minimal clause sequences can be generated with polynomial delay.

In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable to achieve optimal social welfare without a central tie-breaking coordinator. In the case of two buyers with rank valuations, we give polynomial-time algorithms that always find such prices when one of the matroids is a simple partition matroid or both matroids are strongly base orderable. This result partially answers a question raised by Düetting and Végh in 2017. We further formalize a weighted variant of the conjecture of Düetting and Végh, and show that the weighted variant can be reduced to the unweighted one based on the weight-splitting theorem for weighted matroid intersection by Frank. We also show that a similar reduction technique works for M${}^\natural$-concave functions, or equivalently, gross substitutes functions.

We investigate the approximability of the linear 3-cut problem in directed graphs, which is the simplest unsolved case of the linear k-cut problem. The input here is a directed graph D = (V, E) with node weights and three specified terminal nodes s,r,t ∊ V, and the goal is to find a minimum weight subset of non-terminal nodes whose removal ensures that s cannot reach r and t, and r cannot reach t. The problem is approximation-equivalent to the problem of blocking rooted in- and out-arborescences, and it also has applications in network coding and security. The approximability of linear 3-cut has been wide open until now: the best known lower bound under the Unique Games Conjecture (UGC) was 4/3, while the best known upper bound was 2 using a trivial algorithm. In this work we completely close this gap: we present a -approximation algorithm and show that this factor is tight assuming UGC. Our contributions are twofold: (1) we analyze a natural two-step deterministic rounding scheme through the lens of a single-step randomized rounding scheme with non-trivial distributions, and (2) we construct integrality gap instances that meet the upper bound of . Our gap instances can be viewed as a weighted graph sequence converging to a “graph limit structure”.

We present a routing system that considers uncertainties, which are prevalent in any real transport system. Given desired departure or arrival times and a utility function representing the traveller’s preferences, our method computes not just a single path through the network, but a more sophisticated and adaptive journey plan called routing policy. For each stop and time instance, a policy specifies the list of services that the passenger is recommended to take. We show that the problem of finding an optimal policy is NP-hard. We also give a polynomial-time algorithm for a relaxation of the problem when the number of recommended services is limited at each stop and time. A computational case study for the public transport network of Budapest shows that the obtained routing policies can lead to substantial travel time savings compared to deterministic plans, and that considering multiple service policies leads to an improvement compared to previous solutions using single-service policies.

The Dulmage--Mendelsohn decomposition (or the DM-decomposition) gives a unique partition of the vertex set of a bipartite graph reflecting the structure of all the maximum matchings therein. A bipartite graph is said to be DM-irreducible if its DM-decomposition consists of a single component. In this paper, we focus on the problem of making a given bipartite graph DM-irreducible by adding edges. When the input bipartite graph is balanced (i.e., both sides have the same number of vertices) and has a perfect matching, this problem is equivalent to making a directed graph strongly connected by adding edges, for which the minimum number of additional edges was characterized by Eswaran and Tarjan [ SIAM J. Comput., 5 (1976), pp. 653--665]. We give a general solution to this problem, which is divided into three parts. We first show that our problem can be formulated as a special case of a general framework of covering supermodular functions, which was introduced by Frank and Jordán [ J. Combin. Theory Ser. B, 65 (1995), pp. 73--110] to investigate the directed connectivity augmentation problem. Second, when the input graph is not balanced, the problem is solved via matroid intersection. This result can be extended to the minimum cost version in which the addition of an edge gives rise to an individual cost. Third, for balanced input graphs, we devise a combinatorial algorithm that finds a minimum number of additional edges to attain the DM-irreducibility, while the minimum cost version of this problem is NP-hard. These results also lead to min-max characterizations of the minimum number, which generalize the result of Eswaran and Tarjan.

The computational complexity of multicut-like problems may vary significantly depending on whether the terminals are fixed or not. In this work we present a comprehensive study of this phenomenon in two types of cut problems in directed graphs: double cut and bicut. 1. Fixed-terminal edge-weighted double cut is known to be solvable efficiently. We show that fixed-terminal node-weighted double cut cannot be approximated to a factor smaller than 2 under the Unique Games Conjecture (UGC), and we also give a 2-approximation algorithm. For the global version of the problem, we prove an inapproximability bound of 3/2 under UGC. 2. Fixed-terminal edge-weighted bicut is known to have an approximability factor of 2 that is tight under UGC. We show that the global edge-weighted bicut is approximable to a factor strictly better than 2, and that the global node-weighted bicut cannot be approximated to a factor smaller than 3/2 under UGC. 3. In relation to these investigations, we also prove two results on undirected graphs which are of independent interest. First, we show NP-completeness and a tight inapproximability bound of 4/3 for the node-weighted 3-cut problem under UGC. Second, we show that for constant k, there exists an efficient algorithm to solve the minimum {s,t}-separating k-cut problem. Our techniques for the algorithms are combinatorial, based on LPs and based on the enumeration of approximate min-cuts. Our hardness results are based on combinatorial reductions and integrality gap instances.

In the k disjoint shortest paths problem (k-DSPP), we are given a graph and its vertex pairs (s_1, t_1), ... , (s_k, t_k), and the objective is to find k pairwise disjoint paths P_1, ... , P_k such that each path P_i is a shortest path from s_i to t_i, if they exist. If the length of each edge is equal to zero, then this problem amounts to the disjoint paths problem, which is one of the well-studied problems in algorithmic graph theory and combinatorial optimization. Eilam-Tzoreff (1998) focused on the case when the length of each edge is positive, and showed that the undirected version of 2-DSPP can be solved in polynomial time. Polynomial solvability of the directed version was posed as an open problem by Eilam-Tzoreff (1998). In this paper, we solve this problem affirmatively, that is, we give a first polynomial time algorithm for the directed version of 2-DSPP when the length of each edge is positive. Note that the 2 disjoint paths problem in digraphs is NP-hard, which implies that the directed 2-DSPP is NP-hard if the length of each edge can be zero. We extend our result to the case when the instance has two terminal pairs and the number of paths is a fixed constant greater than two. We also show that the undirected k-DSPP and the vertex-disjoint version of the directed k-DSPP can be solved in polynomial time if the input graph is planar and k is a fixed constant.

Edmonds's fundamental theorem on arborescences in [J. Edmonds, Edge-disjoint branchings, in Combinatorial Algorithms, Courant Comput. Sci. Sympos. 9, Algorithmics Press, New York, 1973, pp. 91--96] characterizes the existence of $k$ pairwise arc-disjoint spanning arborescences with the same root in a directed graph. In [L. Lovász, J. Combinatorial Theory Ser. B, 21 (1976), pp. 96--103], Lovász gave an elegant alternative proof which became the basis of many extensions of Edmonds's result. In this paper, we use a modification of Lovász's method to prove a theorem on covering intersecting bi-set families under matroid constraints. Our result can be considered as an extension of previous results on packing arborescences. We also investigate the algorithmic aspects of the problem and present a polynomial-time algorithm for solving the corresponding optimization problem.