Search

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

In a recent paper, Avis, Bremner, Tiwary and Watanabe gave a method for constructing linear programs (LPs) based on algorithms written in a simple programming language called Sparks. If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size and its optimum solution contains x as well as a complete execution trace of the algorithm. Their method led us to the construction of a compiler called sparktope which we describe in this paper. This compiler allows one to generate polynomial sized LPs for problems in P that have exponential extension complexity, such as matching problems in non-bipartite graphs. In this paper, we describe sparktope, the language Sparks, and the assembler instructions and LP constraints it produces. This is followed by two concrete examples, the makespan problem and the problem of testing if a matching in a graph is maximum, both of which are known to have exponential extension complexity. Computational results are given. In discussing these examples, we make use of visualization techniques included in sparktope that may be of independent interest. The extremely large linear programs produced by the compiler appear to be quite challenging to solve using currently available software. Since the optimum LP solutions can be computed independently they may be useful as benchmarks. Further enhancements of the compiler and its application are also discussed. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimal subcarrier allocation in OFDMA systems to achieve the minimum outage probability while guaranteeing fairness. The optimal subcarrier allocation algorithm and the maximum frequency diversity gain are both analyzed through the maximum matching method based on the random bipartite graph theory. Accordingly, a surprising result is found, which shows that the maximum frequency diversity gain in subcarrier-sharing OFDMA systems is the same as that in point-to-point OFDM systems that serve only one user by using N subcarriers. It is then demonstrated that this maximum frequency diversity gain can be achieved by a proposed Random Vertex Rotation based Hopcroft-Karp (RVRHK) algorithm with the time complexity of O(N2.5), where N is the number of subcarriers. Because the theoretical analysis and the RVRHK algorithm are both based on the maximum matching method, the maximum frequency diversity in OFDMA systems is referred to as the max-matching diversity in this paper. [ABSTRACT FROM AUTHOR]

In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results by Karp and Sipser suggest that the first algorithm is superior. In this paper we show that this is indeed the case, at least for random k‐regular graphs. We show that w.h.p. the first algorithm will find a matching of size n/2−O(logn) in a random k‐regular graph, k = O(1). We also show that the algorithm can be adapted to find a maximum matching in O(n) time w.h.p. This is to be compared with O(n3/2) time for the worst‐case. [ABSTRACT FROM AUTHOR]

Nowadays, large cities face numerous problems caused by the rapidly increasing number of vehicles on road. Carpooling has been shown as an efficient solution to ease the traffic pressure. The objective of our carpool scheduling problem is to minimise the number of carpools needed to transport users. Previous research on the similar topic introduces static capacity constraint which limits the carpool size to the vehicle's capacity. However, it is unnecessary since a seat in the vehicle can be occupied by several passengers if their routes are not overlapped. In this paper, we remove this constraint, which allows a vehicle to serve more users than its capacity. We propose a greedy approach based on the iterative matching and merging. Specifically, starting from a set of single-user carpools, the algorithm iteratively checks the merge-ability between carpools, and then applies the maximum matching algorithm to maximise the number of carpools merged. In addition, two methods are proposed to reduce the time complexity of merge-ability checking process. Furthermore, we improve the time efficiency of our algorithms by exploiting geometry properties. Experimental results on synthetic and real-world datasets show that our algorithms have better performances than baseline. [ABSTRACT FROM AUTHOR]

Most of works on the time complexity analysis of evolutionary algorithms have always focused on some artificial binary problems. The time complexity of the algorithms for combinatorial optimisation has not been well understood. This paper considers the time complexity of an evolutionary algorithm for a classical combinatorial optimisation problem, to find the maximum cardinality matching in a graph. It is shown that the evolutionary algorithm can produce a matching with nearly maximum cardinality in average polynomial time. [ABSTRACT FROM AUTHOR]

A critical prerequisite for controlling complex networks is to find a driver node set with a structural controllability guarantee. This paper introduces the control capacity for a driver node set and solves the problem of finding a complete minimum driver node set that not only guarantees network structural controllability but achieves the desired level of control capacity. A novel algorithmic framework is proposed which is based on the concept of equivalent set and approximate matching replacement technique. The proposed algorithmic framework is shown to outperform the state-of-the-art approaches in the literature. The validity of the proposed algorithm is analyzed and the performance is evaluated by experiments on artificial and real-world complex networks. [ABSTRACT FROM AUTHOR]

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph $$G= (A\, \dot{\cup }\, P, E)$$ with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between $$\textsf {NP}$$ -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $$u_{\max }$$ as basis, and we prove that this dependence is necessary unless $$\textsf {FPT}= \textsf {W}[1]$$ . The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee $$u_{\max }+1$$ , which is asymptotically best possible unless $$\textsf {P}= \textsf {NP}$$ . Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas. [ABSTRACT FROM AUTHOR]

A connected graph $$G$$ is said to be factor-critical if $$G-v$$ has a perfect matching for every vertex $$v$$ of $$G$$ . Lovász proved that every factor-critical graph has an ear decomposition. In this paper, the ear decomposition of the factor-critical graphs $$G$$ satisfying that $$G-v$$ has a unique perfect matching for any vertex $$v$$ of $$G$$ with degree at least 3 is characterized. From this, the number of maximum matchings of factor-critical graphs with the special ear decomposition is obtained. [ABSTRACT FROM AUTHOR]

Recently, an ancient slime mold, Physarum polycephalum, has been proved being capable of finding shortest path in physical maze environment, which inspires researchers to extract the core foraging mechanism -- positive feedback -- to simulate or model such intelligent behavior. Among most wellknown mathematical models developed so far, physarum solver, has been adopted and extended to solve a plethora of optimization problems in different fields, including computer science, operations research and transportation etc. In this paper, we first adopt and apply a variant of modified physarum solver, called iterative physarum model, to solve bipartite matching problem. Specifically, the maximum bipartite matching problem is first equivalently transformed to single-source single-sink maximum flow problem. Then the iterative physarum model is used to solve the maximum flow problem adaptively. As iterative physarum solver does not involve solving the systems of linear equations associated with global network flow balance constraints, time complexity of updating node status for one iteration can be reduced from O(n3) to O(m), where n and m are numbers of nodes and edges in the graph, respectively. Extensive numerical studies on both sparse and complete bipartite graphs demonstrate the validity and efficiency of this method [ABSTRACT FROM AUTHOR]

A matching $${E_\mathcal{M}}$$ of graph G = ( V, E) is a subset of the edges E, such that no vertex in V is incident to more than one edge in $${E_\mathcal{M}}$$ . The matching $${E_\mathcal{M}}$$ is maximum if there is no matching in G with size strictly larger than the size of $${E_\mathcal{M}}$$ . In this paper, we present a distributed stabilizing algorithm for finding maximum matching in bipartite graphs based on the stabilizing PIF algorithm of Cournier et al. (Proceedings of 21st IEEE international conference on distributed computing systems, 91–98, 2001). Since our algorithm is stabilizing, it does not require initialization and withstands transient faults. The complexity of the proposed algorithm is O( d × n) rounds, where d is the diameter of the communication network and n is the number of nodes in the network. The space complexity is O(log Δ + log d), where Δ is the largest degree of all the nodes in the communication network. In addition, an optimal version of the proposed algorithm finding maximum matching in linear time is also presented. [ABSTRACT FROM AUTHOR]

Recent works have shown that cooperative diversity can be achieved by using relay selection (RS), distributed space-time coding (DSTC), and distributed beam-forming (DBF) in narrow-band decode-and-forward (DF) cooperative networks with one source-and-destination (s-d) pair. However, the joint resource allocation for broadband DF cooperative networks with multiple s-d flows has not received much attention yet. In this paper, a random hypergraph based unified matching framework is proposed, under which five feasible types of multi-flow DF cooperative networks will be considered. In each type, the maximum matching method will be applied to RS, DSTC, and DBF schemes so as to achieve the optimal channel allocation and relay selection with fairness assurance. By analyzing the properties of maximum matching, the outage probability of each s-d pair after resource allocation will be obtained. The results of diversity-multiplexing tradeoff will show that the proposed framework is capable of achieving the full frequency diversity and cooperative diversity for each s-d pair simultaneously, while the frequency multiplexing is equally shared. Based on the unified framework, the random rotation based parallel Hopcroft-Karp (Rsuperscript2PHK) algorithm will then be designed, which can work in each destination node independently, and shall enjoy a poly-logarithmic complexity \mathcalO(\log^2l0N), where N is the number of channels and l0 is a constant. [ABSTRACT FROM AUTHOR]

Abstract: Greedy scheduling heuristics provide a low complexity and scalable albeit particularly sub-optimal strategy for hardware-based crossbar schedulers. In contrast, the maximum matching algorithm for Bipartite graphs can be used to provide optimal scheduling for crossbar-based interconnection networks with a significant complexity and scalability cost. In this paper, we show how maximum matching can be reformulated in terms of Boolean operations rather than the more traditional formulations. By leveraging the inherent parallelism available in custom hardware design, we reformulate maximum matching in terms of Boolean operations rather than matrix computations and introduce three maximum matching implementations in hardware. Specifically, we examine a Pure Logic Scheduler with three dimensions of parallelism, a Matrix Scheduler with two dimensions of parallelism and a Vector Scheduler with one dimension of parallelism. These designs reduce the algorithmic complexity for an network from to , , and , respectively, where is the number of optimization steps. While an optimal scheduling algorithm requires steps, by starting with our hardware-based greedy strategy to generate an initial schedule, our simulation results show that the maximum matching scheduler can achieve 99% of the optimal schedule when . We examine hardware and time complexity of these architectures for crossbar sizes of up to . Using FPGA synthesis results, we show that a greedy schedule for crossbars, ranging from 8×8 to 256×256, can be optimized in less than 20 ns per optimization step. For crossbars reaching 1024×1024 the scheduling can be completed in approximately 10 μs with current technology and could reach under 90 ns with future technologies. [Copyright &y& Elsevier]

Controlling complex networks are one of the ultimate goals in network science. Previous works have found there exist two distinct control modes when controlling the dense networks: distributed and centralized modes. How to change the control mode of a network is a challenging problem. This paper presents an efficient algorithm to alter a network from distributed mode to centralized mode by reversing the direction of a few edges. We first analyze four possible cases when reversing an edge and then design an efficient algorithm to change the control mode of a network. We prove that our algorithm does not affect the control scheme of the network after mode change. We evaluate the performance of our algorithm on both synthetic and real networks. The results show that the control mode of most networks can be easily changed by reversing very few edges. Furthermore, the number of the possible driver nodes of the network after mode change is dramatically decreased, which means these networks are easier to control. Our algorithm provides the ability to design the desired control mode of a network for different control scenarios, which may be used in many applications. • We present a novel algorithm to change the control mode of a network by reversing the edges. • The control scheme remains unchanged when we change a network from distributed mode to centralized mode. • The results showed our algorithms are efficient and effective to change the control mode of complex networks. [ABSTRACT FROM AUTHOR]

Due to the potential of enhancing traffic safety, protecting environment, and enabling new applications, vehicular communications, especially vehicle-to-vehicle (V2V) communications, has recently been receiving much attention. Because of both safety and non-safety real-time applications, V2V communications has QoS requirements on rate, latency, and reliability. How to appropriately design channel allocation is therefore a key MAC/PHY layer issue in vehicular communications. The QoS requirements of real-time V2V communications can be met by achieving a low outage probability and high outage capacity. In this paper, we first formulate the subchannel allocation in V2V communications into a maximum matching problem on random bipartite graphs. A distributed shuffling based Hopcroft-Karp (DSHK) algorithm will then be proposed to solve this problem with a sub-linear complexity of O(N^2/3), where N is the number of subchannels. By studying the maximum matching generated by the DSHK algorithm on random bipartite graphs, the outage probabilities are derived in the high (two near vehicles) and low (two far away vehicles) SNR regimes, respectively. It is then demonstrated that the proposed method has a similar outage performance as the scenario of two communicating vehicles occupying N subchannels. By solving high degree algebraic equations, the outage capacity can be obtained to determine the maximum traffic rate given an outage probability constraint. It is also shown that the proposed scheme can take an advantage of small signaling overhead with only one-bit channel state information broadcasting for each subchannel. [ABSTRACT FROM AUTHOR]

In the adversarial edge arrival model for maximum cardinality matching, edges of an unknown graph are revealed one-by-one in an arbitrary order, and should be irrevocably accepted or rejected. Here, the goal of an online algorithm is to maximize the number of accepted edges while maintaining a feasible matching at any point in time. For this model, the standard greedy heuristic is 1 2 -competitive, and on the other hand, no algorithm that outperforms this ratio is currently known, even for very simple graphs. We present a clean Min-Index framework for devising a family of randomized algorithms, and provide a number of positive and negative results in this context. Among these results, we present a 5 9 -competitive algorithm when the underlying graph is a forest, and prove that this ratio is best possible within the Min-Index framework. In addition, we prove a new general upper bound of 2 3 + 1 / ϕ 2 ≈ 0.5914 on the competitiveness of any algorithm in the edge arrival model. Interestingly, while this result slightly falls short of the currently best 1 1 + ln 2 ≈ 0.5906 bound by Epstein et al. (Inf Comput 259(1):31–40, 2018), it holds even for an easier model in which vertices along with their adjacent edges arrive online. As a result, we improve on the currently best upper bound of 0.6252 for the latter model, due to Wang and Wong (in: Proceedings of the 42nd ICALP, 2015). [ABSTRACT FROM AUTHOR]

Since Tinhofer proposed the MinGreedy algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and benchmark instances. In contrast, only few analytical results are known. We show that MinGreedy cannot improve on the trivial approximation ratio of $$\frac{1}{2}$$ whp., even for bipartite graphs. Our hard inputs seem to require a small number of high-degree nodes. This motivates an investigation of greedy algorithms on graphs with maximum degree $$\varDelta $$ : we show that MinGreedy achieves a $${\frac{{\varDelta }-1}{2{\varDelta }-3}} $$ -approximation for graphs with $${\varDelta } {=} 3$$ and for $$\varDelta $$ -regular graphs, and a guarantee of $${\frac{{\varDelta }-1/2}{2{\varDelta }-2}} $$ for graphs with maximum degree $${\varDelta } $$ . Interestingly, our bounds even hold for the deterministic MinGreedy that breaks all ties arbitrarily. Moreover, we investigate the limitations of the greedy paradigm, using the model of priority algorithms introduced by Borodin, Nielsen, and Rackoff. We study deterministic priority algorithms and prove a $${\frac{{\varDelta }-1}{2{\varDelta }-3}}$$ -inapproximability result for graphs with maximum degree $${\varDelta } $$ ; thus, these greedy algorithms do not achieve a $$\frac{1}{2} {+} \varepsilon $$ -approximation and in particular the $$\frac{2}{3}$$ -approximation obtained by the deterministic MinGreedy for $${\varDelta } {=} 3$$ is optimal in this class. For k-uniform hypergraphs we show a tight $$\frac{1}{k}$$ -inapproximability bound. We also study fully randomized priority algorithms and give a $$\frac{5}{6}$$ -inapproximability bound. Thus, they cannot compete with matching algorithms of other paradigms. [ABSTRACT FROM AUTHOR]

We prove $$n^{1+\varOmega (1/p)}/p^{O(1)}$$ lower bounds for the space complexity of p-pass streaming algorithms solving the following problems on n-vertex graphs: (1) testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size), (2) testing if two specific vertices are at distance at most $$2(p+1)$$ in an undirected graph, (3) testing if there is a directed path from s to t for two specific vertices s and t in a directed graph. The lower bounds hold for $$p = O(\log n / \log \log n)$$ . Prior to our result, it was known that these problems require $$\varOmega (n^2)$$ space in one pass, but no $$n^{1+\varOmega (1)}$$ lower bound was known for any $$p\ge 2$$ . These streaming results follow from a communication complexity lower bound for a communication game in which the players hold two graphs on the same set of vertices. The task of the players is to find out whether the sets of vertices at distance exactly $$p+1$$ from a specific vertex intersect. The game requires a significant amount of communication only if the players are forced to speak in a specific difficult order. This is reminiscent of lower bounds for communication problems such as indexing and pointer chasing. Among other things, our line of attack requires proving an information cost lower bound for a decision version of the classic pointer chasing problem and a direct sum type theorem for the disjunction of several instances of this problem. [ABSTRACT FROM AUTHOR]

We present an O( nlog n)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O( rnlog n) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in $O(\sqrt{n}m)$-time for graphs with m edges, whenever m= ω( rnlog n). [ABSTRACT FROM AUTHOR]

We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices n. We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity O (d²), where d is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error ∈n for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to d and 1/∈. Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least Ω(n)queries. [ABSTRACT FROM AUTHOR]

We introduce two new classes of graphs which we call convex-round, respectively concave-round graphs. Convex-round (concave-round) graphs are those graphs whose vertices can be circularly enumerated so that the (closed) neighborhood of each vertex forms an interval in the enumeration. Hence the two classes transform into each other by taking complements. We show that both classes of graphs have nice structural properties. We observe that the class of concave-round graphs properly contains the class of proper circular arc graphs and, by a result of Tucker [Pacific J. Math., 39 (1971), pp. 535-545] is properly contained in the class of general circular arc graphs. We point out that convex-round and concave-round graphs can be recognized in O(n + m) time (here n denotes the number of vertices and m the number of edges of the graph in question). We show that the chromatic number ofa graph which is convex-round (concave-round) can be found in time O(n + m) (O(n²)). We describe optimal O(n + m) time algorithms for finding a maximum clique, a maximum matching, and a Hamiltonian cycle (if one exists) for the class of convex-round graphs. Finally, we pose a number of open problems and conjectures concerning the structure and algorithmic properties of the two new classes and a related third class of graphs. [ABSTRACT FROM AUTHOR]

Let S = {C[SUB1],C[SUB2],...,C[SUBk]} be a collection of pairwise disjoint subsets of U = {1,2,...,n} such that ∪[SUPk,SUBi=1] Ci = U. A partition matching of S consists of two subsets {a[SUB1],...,a[SUBm]} and {b[SUB1],...,b[SUBm]} of U together with a sequence of distinct partitions of S: (A[SUB1], B[SUB1]),..., (A[SUBm], B[SUBm]) such that a[SUBi] is contained in a subset in the collection A[SUBi] and b[SUBi] is contained in a subset in the collection B[SUBi] for all i = 1,...,m. An efficient algorithm is developed that constructs a maximum partition matching for a given collection S. The algorithm can be used to construct optimal parallel routing between two nodes in interconnection networks. [ABSTRACT FROM AUTHOR]

The article proposes an approach to calculate the density. It investigates how the approach is used in verifying conditions for the existence of a continuous service schedule. It uses a fast algorithm to calculate the maximum density subgraph of the graph G. It argues that if M is the is the time required in determining the minimal cut bandwidth of a network with vertices and edges, then the algorithm developed calculates the value of density over time.