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.

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.

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.

Abstract. We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Kamiyama [ Theoret. Comput. Sci., 809 (2020), pp. 265–276] and solved in the special case where matroids are base orderable. Utilizing a newly shown matroid exchange property, we show that the problem is tractable for arbitrary matroids. We further investigate a different notion of popularity, where the agents vote with respect to lexicographic preferences, and show that both existence and verification problems become coNP-hard even in the [Formula: see text]-matching case.

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.

We consider a matching problem in a bipartite graph G = (A∪B, E) where each node in A is an agent having preferences in partial order over her neighbors, while nodes in B are objects with no preferences. The size of our matching is more important than node preferences–thus, we are interested in maximum matchings only. Any pair of maximum matchings in G (equivalently, perfect matchings or assignments) can be compared by holding a head-to-head election between them where agents are voters. The goal is to compute an assignment such that there is no better or “more popular” assignment. This is the popular assignment problem and it generalizes the well-studied popular matching problem (Abraham et al., 2007). Popular assignments need not exist in every input instance. We show a polynomial-time algorithm that decides if the given instance admits one or not, and computes one, if so. In instances with no popular assignment, we consider the problem of finding an almost popular assignment, i.e., an assignment with minimum unpopularity margin. We show an O∗ (|E|k) time algorithm for deciding if there exists an assignment with unpopularity margin at most k. We then show that this algorithm is essentially optimal by proving that the problem is NP-complete and Wl[1]-hard with parameter k. We also consider the minimum-cost popular assignment problem when there are edge costs, and show this problem to be NP-hard. This hardness holds even when all edge costs are in {0,1} and agents have strict preferences. By contrast, we propose a polynomial-time algorithm to the problem of deciding if there exists a popular assignment with a given set of forced/forbidden edges (this tractability holds even for partially ordered preferences). Our algorithms are combinatorial and based on LP duality. They search for an appropriate witness or dual certificate, and when a certificate cannot be found, we prove that the desired assignment does not exist in G.

Abstract LetGbe a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences overbranchings, i.e., directed forests; a branchingBispopularifBdoes not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide ifGadmits a popular branching or not. We give a characterization of popular branchings in terms ofdual certificatesand use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate thepopular branching polytopein the original space and also show that our algorithm can be modified to compute a branching withleast unpopularity margin. When preferences are strict rankings, we show that “approximately popular” branchings always exist.

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”.

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.

Given a digraph D = (V, A) and a positive integer k, an arc set F ⊆ A is called a k-arborescence if it is the disjoint union of k spanning arborescences. The problem of finding a minimum cost k-arborescence is known to be polynomial-time solvable using matroid intersection. In this paper we study the following problem: find a minimum cardinality subset of arcs that contains at least one arc from every minimum cost k-arborescence. For k = 1. the problem was solved in [A. Bernáth, G. Pap, Blocking optimal arborescences, IPCO 2013]. In this paper we give an algorithm for general k that has polynomial running time if k is fixed.

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.

We prove two results on packing common bases of two matroids. First, we show that the computational problem of common base packing reduces to the special case where one of the matroids is a direct sum of uniform matroids. Second, we give a counterexample to a conjecture of Chow, which proposed a sufficient condition for the existence of a common base packing. Chow's conjecture is a generalization of Rota's basis conjecture.

Given an undirected hypergraph and a subset of vertices S sube V with a specified root vertex r isin S, the Steiner rooted-orientation problem is to find an orientation of all the hyperedges so that in the resulting directed hypergraph the "connectivity" from the root r to the vertices in S is maximized. This is motivated by a multicasting problem in undirected networks as well as a generalization of some classical problems in graph theory. The main results of this paper are the following approximate min-max relations: middot Given an undirected hypergraph H, if S is 2k-hyperedge-connected in H, then H has a Steiner rooted k-hyperarc-connected orientation. middot Given an undirected graph G, if S is 2k-element-connected in G, then G has a Steiner rooted k-element-connected orientation. Both results are tight in terms of the connectivity bounds. These also give polynomial time constant factor approximation algorithms for both problems. The proofs are based on submodular techniques, and a graph decomposition technique used in the Steiner tree packing problem. Some complementary hardness results are presented at the end