Search

In vertex recoloring, we are given $n$ vertices with their initial coloring, and edges arrive in an online fashion. The algorithm must maintain a valid coloring by recoloring vertices, at a cost. The problem abstracts a scenario of job placement in machines (possibly in the cloud), where vertices represent jobs, colors represent machines, and edges represent ``anti affinity'' (disengagement) constraints. Online recoloring is a hard problem. One family of instances which is fairly well-understood is bipartite graphs, in which two colors are sufficient to satisfy all constraints. In this case it is known that the competitive ratio of vertex recoloring is $\Theta(\log n)$. We propose a generalization of the problem, which allows using additional colors (possibly at a higher cost), to improve overall performance. We analyze the simple case of bipartite graphs of bounded largest \emph{bond} (a bond of a connected graph is an edge-cut that partitions the graph into two connected components). First, we propose two algorithms. One exhibits a trade-off for the uniform-cost case: given $\Omega(\log\beta)\le c\le O(\log n)$ colors, the algorithm guarantees that its cost is at most $O(\frac{\log n}{c})$ times the optimal offline cost for two colors, where $n$ is the number of vertices and $\beta$ is the size of the largest bond. The other algorithm is for the case where the additional colors come at a higher cost, $D>1$: given $\Delta$ additional colors, where $\Delta$ is the maximum degree in the graph, the algorithm guarantees $O(\log D)$ competitiveness. As to lower bounds, we show that if the cost of the extra colors is $D>1$, no (randomized) algorithm can achieve a competitive ratio of $o(\log D)$. We also show that for bipartite graphs of unbounded bond size, any deterministic online algorithm has competitive ratio $\Omega(\min(D,\log n))$.

How can we effectively and efficiently learn node representations in signed bipartite graphs? A signed bipartite graph is a graph consisting of two nodes sets where nodes of different types are positively or negative connected, and it has been extensively used to model various real-world relationships such as e-commerce, etc. To analyze such a graph, previous studies have focused on designing methods for learning node representations using graph neural networks. In particular, these methods insert edges between nodes of the same type based on balance theory, enabling them to leverage augmented structures in their learning. However, the existing methods rely on a naive message passing design, which is prone to over-smoothing and susceptible to noisy interactions in real-world graphs. Furthermore, they suffer from computational inefficiency due to their heavy design and the significant increase in the number of added edges. In this paper, we propose ELISE, an effective and lightweight GNN-based approach for learning signed bipartite graphs. We first extend personalized propagation to a signed bipartite graph, incorporating signed edges during message passing. This extension adheres to balance theory without introducing additional edges, mitigating the over-smoothing issue and enhancing representation power. We then jointly learn node embeddings on a low-rank approximation of the signed bipartite graph, which reduces potential noise and emphasizes its global structure, further improving expressiveness without significant loss of efficiency. We encapsulate these ideas into ELISE, designing it to be lightweight, unlike the previous methods that add too many edges and cause inefficiency. Through extensive experiments on real-world signed bipartite graphs, we demonstrate that ELISE outperforms its competitors for predicting link signs while providing faster training and inference time.

Bipartite graphs are commonly used to model relationships between two distinct entities in real-world applications, such as user-product interactions, user-movie ratings and collaborations between authors and publications. A butterfly (a 2x2 bi-clique) is a critical substructure in bipartite graphs, playing a significant role in tasks like community detection, fraud detection, and link prediction. As more real-world data is presented in a streaming format, efficiently counting butterflies in streaming bipartite graphs has become increasingly important. However, most existing algorithms typically assume that duplicate edges are absent, which is hard to hold in real-world graph streams, as a result, they tend to sample edges that appear multiple times, leading to inaccurate results. The only algorithm designed to handle duplicate edges is FABLE, but it suffers from significant limitations, including high variance, substantial time complexity, and memory inefficiency due to its reliance on a priority queue. To overcome these limitations, we introduce DEABC (Duplicate-Edge-Aware Butterfly Counting), an innovative method that uses bucket-based priority sampling to accurately estimate the number of butterflies, accounting for duplicate edges. Compared to existing methods, DEABC significantly reduces memory usage by storing only the essential sampled edge data while maintaining high accuracy. We provide rigorous proofs of the unbiasedness and variance bounds for DEABC, ensuring they achieve high accuracy. We compare DEABC with state-of-the-art algorithms on real-world streaming bipartite graphs. The results show that our DEABC outperforms existing methods in memory efficiency and accuracy, while also achieving significantly higher throughput.

Community search over bipartite graphs is a fundamental problem, and finding influential communities has attracted significant attention. However, all existing studies have used the minimum weight of vertices as the influence of communities. This leads to an inaccurate assessment of real influence in graphs where there are only a few vertices with low weights. In this paper, we propose a new cohesive subgraph model named ($\alpha$,$\beta$)-influential community that considers the average weight of vertices from two layers on bipartite graphs, thereby providing a more comprehensive reflection of community influence. Based on this community model, we present a recursive algorithm that traverses the entire bipartite graph to find top-$r$ ($\alpha$,$\beta$)-influential communities. To further expedite the search for influential communities, we propose a slim tree structure to reduce the search width and introduce several effective upper bounds to reduce the search depth. Since we have proven that this problem is NP-hard, using exact algorithms to find top-$r$ ($\alpha$,$\beta$)-communities accurately is very time-consuming. Therefore, we propose an approximate algorithm using a greedy approach to find top-$r$ ($\alpha$,$\beta$)-communities as quickly as possible. It only takes $O((n+m)+m\log_{}{n})$ time. Additionally, we introduce a new pruning algorithm to improve the efficiency of the search. Extensive experiments on 10 real-world graphs validate both the effectiveness and the efficiency of our algorithms.

Let $G$ be a bipartite graph with adjacency matrix $A(G)$. The characteristic polynomial $\phi(G,x)=\det(xI-A(G))$ and the permanental polynomial $\pi(G,x) = \text{per}(xI-A(G))$ are both graph invariants used to distinguish graphs. For bipartite graphs, we define the modified characteristic polynomial, which is obtained by changing the signs of some of the coefficients of $\phi(G,x)$. For $4k$-intercyclic bipartite graphs, i.e., those for which the removal of any $4k$-cycle results in a $C_{4k}$-free graph, we provide an expression for $\pi(G,x)$ in terms of the modified characteristic polynomial of the graph and its subgraphs. Our approach is purely combinatorial in contrast to the Pfaffian orientation method found in the literature to compute the permanental polynomial., Comment: 9 pages

In a recent work on the bipartite Erd\H{o}s-R\'{e}nyi graph, Do et al. (2023) established upper bounds on the number of connected labeled bipartite graphs with a fixed surplus. We use some recent encodings of bipartite random graphs in order to provide a probabilistic formula for the number of bipartite graphs with fixed surplus. Using this, we obtain asymptotics as the number of vertices in each class tend to infinity., Comment: 15 pages, 2 figures

We introduce a new class of algebras arising from graphs, called binomial edge rings. Given a graph $G$ on $d$ vertices with $n$ edges, the binomial edge ring of $G$ is defined to be the subalgebra of the polynomial ring with $2d$ variables generated by the binomials which correspond to $n$ edges. In this paper, we calculate a SAGBI basis for this algebra and obtain an initial algebra associated with this SAGBI basis in the case of complete bipartite graphs. It turns out that such an initial algebra is isomorphic to the Hibi ring of a certain poset. Similar phenomenon also occurs in the context of Pl\"{u}cker algebras, so the framework of binomial edge rings can be interpreted as a kind of its generalization., Comment: 12 pages, 3 figures

We are examining a specific type of graph called a balanced bipartite graph. The balanced bipartite graph, such as $\mathcal{B}$, has two parts, $V_1$ and $V_2$, each containing $n$ vertices, for a total of $2n$ vertices. The degree of a vertex $v$ in $V_1\cup\,V_2$ is denoted by $d_\mathcal{B}(v)$. The minimum degree of any vertex in the graph $\mathcal{B}$ is represented by $\delta(\mathcal{B})$. If $S$ is a subset of $V_1\cup\,V_2$, then the subgraph of $\mathcal{B}$ induced by $S$ is the graph that has $S$ as its vertex set and contains all the edges of $\mathcal{B}$ that have both endpoints in $S$. This subgraph is denoted by $\mathcal{B}[S]$. The forest number of a graph $\mathcal{B}$ is the size of the largest subset of vertices of $\mathcal{B}$ that form an induced forest. We use $f(\mathcal{B})$ to represent the forest number of graph $\mathcal{B}$. A decycling set or a feedback vertex set of a graph is a set of vertices whose removal results in a forest. The smallest possible size of a decycling set of $\mathcal{B}$ is represented by $\nabla(\mathcal{B})$. Finding the decycling number of $\mathcal{B}$ is equivalent to determining the largest order of an induced forest, i.e., $f(\mathcal{B})+\nabla(\mathcal{B})=2n$. In this essay, we study the structure and cardinality of the largest subsets of vertices of graph $\mathcal{B}$ that form induced forests.

Counting the number of $(p, q)$-bicliques (complete bipartite subgraphs) in a bipartite graph is a fundamental problem which plays a crucial role in numerous bipartite graph analysis applications. However, existing algorithms for counting $(p, q)$-bicliques often face significant computational challenges, particularly on large real-world networks. In this paper, we propose a general biclique counting framework, called \npivot, based on a novel concept of node-pivot. We show that previous methods can be viewed as specific implementations of this general framework. More importantly, we propose a novel implementation of \npivot based on a carefully-designed minimum non-neighbor candidate partition strategy. We prove that our new implementation of \npivot has lower worst-case time complexity than the state-of-the-art methods. Beyond basic biclique counting, a nice feature of \npivot is that it also supports local counting (computing bicliques per node) and range counting (simultaneously counting bicliques within a size range). Extensive experiments on 12 real-world large datasets demonstrate that our proposed \npivot substantially outperforms state-of-the-art algorithms by up to two orders of magnitude.

We study the problem of partitioning the edge set of a graph into bipartite subgraphs under certain constraints defined by forbidden subgraphs. These constraints lead to both classical, such as partitioning into independent matchings and complete bipartite subgraphs, and novel partitioning problems. The theoretical framework we provide is motivated by clustering problems of real-world transaction graphs, which can naturally be formulated as edge partitioning problems under certain bipartite graph constraints.

Let $G$ be a graph and $T$ be a spanning tree of $G$. We use $Q(G)=D(G)+A(G)$ to denote the signless Laplacian matrix of $G$, where $D(G)$ is the diagonal degree matrix of $G$ and $A(G)$ is the adjacency matrix of $G$. The signless Laplacian spectral radius of $G$ is denoted by $q(G)$. A necessary and sufficient condition for a connected bipartite graph $G$ with bipartition $(A,B)$ to have a spanning tree $T$ with $d_T(v)\geq k$ for any $v\in A$ was independently obtained by Frank and Gy\'arf\'as (A. Frank, E. Gy\'arf\'as, How to orient the edges of a graph?, Colloq. Math. Soc. Janos Bolyai 18 (1976) 353--364), Kaneko and Yoshimoto (A. Kaneko, K. Yoshimoto, On spanning trees with restricted degrees, Inform. Process. Lett. 73 (2000) 163--165). Based on the above result, we establish a lower bound on the signless Laplacian spectral radius $q(G)$ of a connected bipartite graph $G$ with bipartition $(A,B)$, in which the bound guarantees that $G$ has a spanning tree $T$ with $d_T(v)\geq k$ for any $v\in A$., Comment: 8 pages

For a graph family $\mathcal F$, let $\mathrm{ex}(n,\mathcal F)$ and $\mathrm{spex}(n,\mathcal F)$ denote the maximum number of edges and maximum spectral radius of an $n$-vertex $\mathcal F$-free graph, respectively, and let $\mathrm{EX}(n,\mathcal F)$ and $\mathrm{SPEX}(n,\mathcal F)$ denote the corresponding sets of extremal graphs. Wang, Kang, and Xue showed that if $\mathrm{EX}(n,\mathcal F)$ consists of Tur\'an graphs $T_{n,r}$ plus $O(1)$ edges, then $\mathrm{SPEX}(n,\mathcal F)\subseteq\mathrm{EX}(n,\mathcal F)$ for $n$ large enough. Fang, Tait, and Zhai extended this result by showing if $e(T_{n,r})\le\mathrm{ex}(n,\mathcal F) < e(T_{n,r})+\lfloor n/2r\rfloor$ then $\mathrm{SPEX}(n,\mathcal F)\subseteq\mathrm{EX}(n,\mathcal F)$ for $n$ large enough. In this paper we extend the result further and in many cases we can show that our result is best possible, answering a question of Fang, Tait, and Zhai., Comment: 34 pages, 1 figure

A perfect $H$-tiling in a graph $G$ is a collection of vertex-disjoint copies of a graph $H$ in $G$ that covers all vertices of $G$. Motivated by papers of Bush and Zhao and of Balogh, Treglown, and Wagner, we determine the threshold for the existence of a perfect $K_{h,h}$-tiling of a randomly perturbed bipartite graph with linear minimum degree., Comment: 18 pages, 1 figure

Quantum Monte Carlo (QMC) methods have proven invaluable in condensed matter physics, particularly for studying ground states and thermal equilibrium properties of quantum Hamiltonians without a sign problem. Over the past decade, significant progress has also been made on their rigorous convergence analysis. Heisenberg antiferromagnets (AFM) with bipartite interaction graphs are a popular target of computational QMC studies due to their physical importance, but despite the apparent empirical efficiency of these simulations it remains an open question whether efficient classical approximation of the ground energy is possible in general. In this work we introduce a ground state variant of the stochastic series expansion QMC method, and for the special class of AFM on interaction graphs with an $O(1)$-bipartite component (star-like), we prove rapid mixing of the associated QMC Markov chain (polynomial time in the number of qubits) by using Jerrum and Sinclair's method of canonical paths. This is the first Markov chain analysis of a practical class of QMC algorithms with the loop representation of Heisenberg models. Our findings contribute to the broader effort to resolve the computational complexity of Heisenberg AFM on general bipartite interaction graphs., Comment: 29 pages, 10 figures

Biregular bipartite graphs have been proven to have similar edge distributions to random bipartite graphs and thus have nice pseudorandomness and expansion properties. Thus it is quite desirable to find a biregular bipartite spanning subgraph in a given bipartite graph. In fact, a theorem of Ore implies a structural characterization of such subgraphs in bipartite graphs. In this paper, we demonstrate the existence of biregular bipartite spanning subgraphs in bipartite graphs by employing spectral radius. We also study the existence of spanning trees with restricted degrees and edge-disjoint spanning trees in bipartite graphs via spectral radius.

In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs $\mathcal{H}$ in $K_n$, defined as the minimum number of colours needed to colour the edges of $K_n$ so that every copy of a graph $H\in \mathcal{H}$ intersects some colour class in an odd number of edges. In this paper, we focus on complete bipartite graphs. First, we completely resolve the problem when $\mathcal{H}$ is the family of all spanning complete bipartite graphs on $n$ vertices. We then focus on its subfamilies, that is, $\{K_{t,n-t}\colon t\in T\}$ for a fixed set of integers $T\subseteq [\lfloor n/2 \rfloor]$. We prove that the odd-Ramsey problem is equivalent to determining the maximum dimension of a linear binary code avoiding codewords of given weights, and leverage known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs., Comment: 15 pages

For a positive integer $s$, an $s$-club in a graph $G$ is a set of vertices inducing a subgraph with diameter at most $s$. As generalizations of cliques, $s$-clubs offer a flexible model for real-world networks. This paper addresses the problems of partitioning and disjoint covering of vertices with $s$-clubs on bipartite graphs. First we prove that for any fixed $s \geq 3$ and fixed $k \geq 3$, determining whether the vertices of $G$ can be partitioned into at most $k$ disjoint $s$-clubs is NP-complete even for bipartite graphs. Additionally, we study the Maximum Disjoint $(t,s)$-Club Covering problem (MAX-DCC($t,s$)), which aims to find a collection of vertex-disjoint $(t,s)$-clubs (i.e. $s$-clubs with at least $t$ vertices) that covers the maximum number of vertices in $G$. We prove that it is NP-hard to achieve an approximation factor of $\frac{95}{94} $ for MAX-DCC($t,3$) for any fixed $t\geq 8$ and for MAX-DCC($t,2$) for any fixed $t\geq 5$ even for bipartite graphs. Previously, results were known only for MAX-DCC($3,2$). Finally, we provide a polynomial-time algorithm for MAX-DCC($2,2$).

In this paper, we consider the maximum $k$-edge-colorable subgraph problem. In this problem we are given a graph $G$ and a positive integer $k$, the goal to take $k$ matchings of $G$ such that their union contains maximum number of edges. This problem is NP-hard in cubic graphs, and polynomial time solvable in bipartite graphs as we observe in our paper. We present two NP-hardness results for two versions of this problem where we have weights on edges or color constraints on vertices. In fact, we show that these versions are NP-hard already in bipartite graphs of maximum degree three. In order to achieve these results, we establish a connection between our problems and the problem of construction of special maximum matchings considered in the Master thesis of the author and defended back in 2003., Comment: 18 pages, 14 figures

Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid algorithm proposed with the goal of approximately solving combinatorial optimization problems such as the MAX-CUT problem. It has been considered a potential candidate for achieving quantum advantage in the Noisy Intermediate-Scale Quantum era and has been extensively studied. However, the performance limitations of low-level QAOA have also been demonstrated across various instances. In this work, we first analytically prove the performance limitations of level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. To this end, we derive an upper bound for the approximation ratio based on the average degree of bipartite graphs. Second, we demonstrate that Recursive QAOA (RQAOA), which recursively reduces graph size using QAOA as a subroutine, outperforms the level-1 QAOA. However, the performance of RQAOA exhibits limitations as the graph size increases. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations. Surprisingly, this modified RQAOA always finds the exact maximum cut for any bipartite graphs and even for a more general graph with parity-signed weights., Comment: 16 pages, 3 figures

An antimagic labelling of a graph is a bijection from the set of edges to $\{1, 2, \ldots , m\}$, such that all vertex-sums are pairwise distinct, where the vertex-sum of a vertex is the sum of labels on the edges incident to it. We say a graph is antimagic if it has an antimagic labelling. In 2023, it has been proven that connected $(k, l)$-bipartite graphs are antimagic if $k \geq l + 2$ and one of k or l is odd. In this paper, we extend those results to connected (3, 2)-bipartite graphs.

A bipartite graph is chordal bipartite if every cycle of length at least six contains a chord. We determine the minimum size in 2-connected chordal bipartite graphs with given order., Comment: 9 pages.3 figures

A seminal result of Lee asserts that the Ramsey number of any bipartite $d$-degenerate graph $H$ satisfies $\log r(H) = \log n + O(d)$. In particular, this bound applies to every bipartite graph of maximal degree $\Delta$. It remains a compelling challenge to identify conditions that guarantee that an $n$-vertex graph $H$ has Ramsey number linear in $n$, independently of $\Delta$. Our contribution is a characterization of bipartite graphs with linear-size Ramsey numbers in terms of graph bandwidth, a notion of local connectivity. We prove that for any $n$-vertex bipartite graph $H$ with maximal degree at most $\Delta$ and bandwidth $b(H)$ at most $\exp(-C\Delta\log\Delta)\,n$, we have $\log r(H) = \log n + O(1)$. This characterization is nearly optimal: for every $\Delta$ there exists an $n$-vertex bipartite graph $H$ of degree at most $\Delta$ and $b(H) \leq \exp(-c\Delta)\,n$, such that $\log r(H) = \log n + \Omega(\Delta)$. We also provide bounds interpolating between these two bandwidth regimes., Comment: Main result of the paper is known (due to Choongbum Lee, arXiv:1504.06285)

We compute the quadratic embedding constant for complete bipartite graphs with disjoint edges removed. Moreover, we study the quadratic embedding property for theta graphs, i.e., graphs consisting of three paths with common initial points and common endpoints. As a result, we provide an infinite family of primary graphs which are not quadratically embeddable.

In the sandpile model, vertices of a graph are allocated grains of sand. At each unit of time, a grain is added to a randomly chosen vertex. If that causes its number of grains to exceed its degree, that vertex is called unstable, and topples. In the Abelian sandpile model (ASM), topplings are deterministic, whereas in the stochastic sandpile model (SSM) they are random. We study the ASM and SSM on complete bipartite graphs. For the SSM, we provide a stochastic version of Dhar's burning algorithm to check if a given (stable) configuration is recurrent or not, with linear complexity. We also exhibit a bijection between sorted recurrent configurations and pairs of compatible Ferrers diagrams. We then provide a similar bijection for the ASM, and also interpret its recurrent configurations in terms of labelled Motzkin paths., Comment: 19 pages, 9 figures

Alon and Krivelevich conjectured that if $G$ is a bipartite graph of maximum degree $\Delta$, then the choosability (or list chromatic number) of $G$ satisfies $\chi_{\ell}(G) = O \left ( \log \Delta \right )$. Currently, the best known upper bound for $\chi_{\ell}(G)$ is $(1 + o(1)) \frac{\Delta}{\log \Delta}$, which also holds for the much larger class of triangle-free graphs. We prove that for $\varepsilon = 10^{-3}$, every bipartite graph $G$ of sufficiently large maximum degree $\Delta$ satisfies $\chi_{\ell}(G) < (\frac{4}{5} -\varepsilon) \frac{\Delta}{\log \Delta}$. This improved upper bound suggests that list coloring is fundamentally different for bipartite graphs than for triangle-free graphs and hence gives a step toward solving the conjecture of Alon and Krivelevich., Comment: 8 pages

A signed graph is one that features two types of edges: positive and negative. Balanced signed graphs are those in which all cycles contain an even number of positive edges. In the adjacency matrix of a signed graph, entries can be $0$, $-1$, or $1$, depending on whether $ij$ represents no edge, a negative edge, or a positive edge, respectively. The index of the adjacency matrix of a signed graph $\dot{G}$ is less or equal to the index of the adjacency matrix of its underlying graph $G$, i.e., $\lambda_1(\dot{G}) \le \lambda_1(G)$. Indeed, if $\dot{G}$ is balanced, then $\lambda_1(\dot{G})=\lambda_1(G)$. This inequality becomes strict when $\dot{G}$ is an unbalanced signed graph. Recently, Brunetti and Stani\'c found the whole list of unbalanced signed graphs on $n$ vertices with maximum (resp. minimum) spectral radius. To our knowledge, there has been little research on this problem when unbalanced signed graphs are confined to specific graph classes. In this article, we demonstrate that there is only one unbalanced signed bipartite graph on $n$ vertices with maximum spectral radius, up to an operation on the signed edges known as switching. Additionally, we investigate unbalanced signed complete bipartite graphs on $n$ vertices with a bounded number of edges and maximum spectral radius, where the negative edges induce a tree.

A biclique in a graph $G$ is a complete bipartite subgraph (not necessarily induced), and the least positive integer $k$ for which the vertex set of $G$ can be partitioned into at most $k$ bicliques is the biclique vertex partition number $bp(G)$ of $G$. We prove that the inequality $reg(S(G))\geq |G|-bp(G)$ holds for every graph $G$, where $S(G)$ is the $1$-subdivision graph of $G$ and $reg(S(G))$ denotes the (Castelnuovo-Mumford) regularity of the graph $S(G)$. In particular, we show that the equality $reg(S(B))=|B|-bp(B)$ holds provided that $B$ is a chordal bipartite graph. Furthermore, for every chordal bipartite graph $B$, we prove that the independence complex of $S(B)$ is either contractible or homotopy equivalent to a sphere, and provide a polynomial time checkable criteria for when it is contractible, and describe the dimension of the sphere when it is not.

We prove that for every ${\gamma > 0}$ there exists $n_0 \in \mathbb{N}$ such that for every ${n \geq n_0}$ any family of up to $\lfloor{n^{\frac12+\gamma}}\rfloor$ trees having at most $(1-\gamma)n$ vertices in each bipartition class can be packed into $K_{n,n}$. As a tool for our proof, we show an approximate bipartite version of the Koml\'os-S\'ark\"ozy-Szemer\'edi Theorem, which we believe to be of independent interest.

In a bipartite graph, a subgraph is an $s$-biplex if each vertex of the subgraph is adjacent to all but at most $s$ vertices on the opposite set. The enumeration of $s$-biplexes from a given graph is a fundamental problem in bipartite graph analysis. However, in real-world data engineering, finding all $s$-biplexes is neither necessary nor computationally affordable. A more realistic problem is to identify some of the largest $s$-biplexes from the large input graph. We formulate the problem as the {\em top-$k$ $s$-biplex search (TBS) problem}, which aims to find the top-$k$ maximal $s$-biplexes with the most vertices, where $k$ is an input parameter. We prove that the TBS problem is NP-hard for any fixed $k\ge 1$. Then, we propose a branching algorithm, named MVBP, that breaks the simple $2^n$ enumeration algorithm. Furthermore, from a practical perspective, we investigate three techniques to improve the performance of MVBP: 2-hop decomposition, single-side bounds, and progressive search. Complexity analysis shows that the improved algorithm, named FastMVBP, has a running time $O^*(\gamma_s^{d_2})$, where $\gamma_s<2$, and $d_2$ is a parameter much smaller than the number of vertex in the sparse real-world graphs, e.g. $d_2$ is only $67$ in the AmazonRatings dataset which has more than $3$ million vertices. Finally, we conducted extensive experiments on eight real-world and synthetic datasets to demonstrate the empirical efficiency of the proposed algorithms. In particular, FastMVBP outperforms the benchmark algorithms by up to three orders of magnitude in several instances.

Given an $r$-colouring of the edges of a graph $G$, we say that it can be partitioned into $p$ monochromatic cycles when there exists a set of $p$ vertex-disjoint monochromatic cycles covering all the vertices of $G$. In the literature of this problem, an edge and a single vertex both count as a cycle. We show that for every $2$-colouring of the edges of a complete balanced bipartite graph, $K_{n,n}$, it can be partitioned into at most 4 monochromatic cycles. This type of question was first studied in 1970 for complete graphs and in 1983, by Gy\'arf\'as and Lehel, for $K_{n,n}$. In 2014, Pokrovskiy, has showed that any $2$-colouring of the edges of $K_{n,n}$ can be partitioned into at most $3$ paths. It turns out that finding monochromatic cycles instead of paths is a natural question that has also being asked for other graphs. In 2015, Schaudt and Stein have showed that at most 14 cycles are necessary., Comment: 17 pages, 21 figures

Let $\mathscr{F}$ be a family of graphs. A graph $G$ is $\mathscr{F}$-free if $G$ does not contain any $F\in \mathcal{F}$ as a subgraph. The Tur\'an number $ex(n, \mathscr{F})$ is the maximum number of edges in an $n$-vertex $\mathscr{F}$-free graph. Let $M_{s}$ be the matching consisting of $ s $ independent edges. Recently, Alon and Frank determined the exact value of $ex(n,\{K_{m},M_{s+1}\})$. Gerbner obtained several results about $ex(n,\{F,M_{s+1}\})$ when $F$ satisfies certain proportions. In this paper, we determine the exact value of $ex(n,\{K_{l,t},M_{s+1}\})$ when $s, n$ are large enough for every $3\leq l\leq t$. When $n$ is large enough, we also show that $ex(n,\{K_{2,2}, M_{s+1}\})=n+{s\choose 2}-\left\lceil\frac{s}{2}\right\rceil$ for $s\ge 12$ and $ex(n,\{K_{2,t},M_{s+1}\})=n+(t-1){s\choose 2}-\left\lceil\frac{s}{2}\right\rceil$ when $t\ge 3$ and $s$ is large enough., Comment: 15 pages, 2 figures

We study vertex sparsification for preserving cuts. Given a graph $G$ with a subset $|T|=k$ of its vertices called terminals, a \emph{quality-$q$ cut sparsifier} is a graph $G'$ that contains $T$, such that, for any partition $(T_1,T_2)$ of $T$ into non-empty subsets, the value of the min-cut in $G'$ separating $T_1$ from $T_2$ is within factor $q$ from the value of the min-cut in $G$ separating $T_1$ from $T_2$. The construction of cut sparsifiers with good (small) quality and size has been a central problem in graph compression for years. Planar graphs and quasi-bipartite graphs are two important special families studied in this research direction. The main results in this paper are new cut sparsifier constructions for them in the high-quality regime (where $q=1$ or $1+\varepsilon$ for small $\varepsilon>0$). We first show that every planar graph admits a planar quality-$(1+\varepsilon)$ cut sparsifier of size $\tilde O(k/\text{poly}(\varepsilon))$, which is in sharp contrast with the lower bound of $2^{\Omega(k)}$ for the quality-$1$ case. We then show that every quasi-bipartite graph admits a quality-$1$ cut sparsifier of size $2^{\tilde O(k^2)}$. This is the second to improve over the doubly-exponential bound for general graphs (previously only planar graphs have been shown to have single-exponential size quality-$1$ cut sparsifiers). Lastly, we show that contraction, a common approach for constructing cut sparsifiers adopted in most previous works, does not always give optimal bounds for cut sparsifiers. We demonstrate this by showing that the optimal size bound for quality-$(1+\varepsilon)$ contraction-based cut sparsifiers for quasi-bipartite graphs lies in the range $[k^{\tilde\Omega(1/\varepsilon)},k^{O(1/\varepsilon^2)}]$, while in previous work an upper bound of $\tilde O(k/\varepsilon^2)$ was achieved via a non-contraction approach.

Flow sparsification is a classic graph compression technique which, given a capacitated graph $G$ on $k$ terminals, aims to construct another capacitated graph $H$, called a flow sparsifier, that preserves, either exactly or approximately, every multicommodity flow between terminals (ideally, with size as a small function of $k$). Cut sparsifiers are a restricted variant of flow sparsifiers which are only required to preserve maximum flows between bipartitions of the terminal set. It is known that exact cut sparsifiers require $2^{\Omega(k)}$ many vertices [Krauthgamer and Rika, SODA 2013], with the hard instances being quasi-bipartite graphs, where there are no edges between non-terminals. On the other hand, it has been shown recently that exact (or even $(1+\varepsilon)$-approximate) flow sparsifiers on networks with just 6 terminals require unbounded size [Krauthgamer and Mosenzon, SODA 2023, Chen and Tan, SODA 2024]. In this paper, we construct exact flow sparsifiers of size $3^{k^{3}}$ and exact cut sparsifiers of size $2^{k^2}$ for quasi-bipartite graphs. In particular, the flow sparsifiers are contraction-based, that is, they are obtained from the input graph by (vertex) contraction operations. Our main contribution is a new technique to construct sparsifiers that exploits connections to polyhedral geometry, and that can be generalized to graphs with a small separator that separates the graph into small components. We also give an improved reduction theorem for graphs of bounded treewidth [Andoni et al., SODA 2011], implying a flow sparsifier of size $O(k\cdot w)$ and quality $O\bigl(\frac{\log w}{\log \log w}\bigr)$, where $w$ is the treewidth.

We explicitly describe cellular minimal free resolutions of certain classes of edge ideals of weighted complete bipartite graphs based on a construction of Visscher. Specifically, we show that Visscher's construction minimally resolves all edge ideals of undirected vertex-weighted complete bipartite graphs, and we characterize the edge-weighted complete bipartite graphs whose edge ideals are minimally resolved by Visscher's construction.

Graph representation learning (GRL) is to encode graph elements into informative vector representations, which can be used in downstream tasks for analyzing graph-structured data and has seen extensive applications in various domains. However, the majority of extant studies on GRL are geared towards generating node representations, which cannot be readily employed to perform edge-based analytics tasks in edge-attributed bipartite graphs (EABGs) that pervade the real world, e.g., spam review detection in customer-product reviews and identifying fraudulent transactions in user-merchant networks. Compared to node-wise GRL, learning edge representations (ERL) on such graphs is challenging due to the need to incorporate the structure and attribute semantics from the perspective of edges while considering the separate influence of two heterogeneous node sets U and V in bipartite graphs. To our knowledge, despite its importance, limited research has been devoted to this frontier, and existing workarounds all suffer from sub-par results. Motivated by this, this paper designs EAGLE, an effective ERL method for EABGs. Building on an in-depth and rigorous theoretical analysis, we propose the factorized feature propagation (FFP) scheme for edge representations with adequate incorporation of long-range dependencies of edges/features without incurring tremendous computation overheads. We further ameliorate FFP as a dual-view FFP by taking into account the influences from nodes in U and V severally in ERL. Extensive experiments on 5 real datasets showcase the effectiveness of the proposed EAGLE models in semi-supervised edge classification tasks. In particular, EAGLE can attain a considerable gain of at most 38.11% in AP and 1.86% in AUC when compared to the best baselines., Comment: 11 pages. Full version of the research paper accepted to KDD 2024

Bipartite graphs are a prevalent modeling tool for real-world networks, capturing interactions between vertices of two different types. Within this framework, bicliques emerge as crucial structures when studying dense subgraphs: they are sets of vertices such that all vertices of the first type interact with all vertices of the second type. Therefore, they allow identifying groups of closely related vertices of the network, such as individuals with similar interests or webpages with similar contents. This article introduces a new algorithm designed for the exhaustive enumeration of maximal bicliques within a bipartite graph. This algorithm, called BBK for Bipartite Bron-Kerbosch, is a new extension to the bipartite case of the Bron-Kerbosch algorithm, which enumerates the maximal cliques in standard (non-bipartite) graphs. It is faster than the state-of-the-art algorithms and allows the enumeration on massive bipartite graphs that are not manageable with existing implementations. We analyze it theoretically to establish two complexity formulas: one as a function of the input and one as a function of the output characteristics of the algorithm. We also provide an open-access implementation of BBK in C++, which we use to experiment and validate its efficiency on massive real-world datasets and show that its execution time is shorter in practice than state-of-the art algorithms. These experiments also show that the order in which the vertices are processed, as well as the choice of one of the two types of vertices on which to initiate the enumeration have an impact on the computation time., Comment: 21 pages, 4 figures, 3 tables

Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as a temporal bipartite graph. However, the temporal information is widely neglected by previous studies. Moreover, directly extending the existing models may fail to find some critical groups in temporal bipartite graphs, which appear in a unilateral (i.e., one-layer) form. To fill the gap, in this paper, we propose a novel model, called maximal \lambda-frequency group (MFG). Given a temporal bipartite graph G=(U,V,E), a vertex set V_S \subseteq V is an MFG if i) there are no less than \lambda timestamps, at each of which V_S can form a (t_U,t_V)-biclique with some vertices in U at the corresponding snapshot, and ii) it is maximal. To solve the problem, a filter-and-verification (FilterV) method is proposed based on the Bron-Kerbosch framework, incorporating novel filtering techniques to reduce the search space and array-based strategy to accelerate the frequency and maximality verification. Nevertheless, the cost of frequency verification in each valid candidate set computation and maximality check could limit the scalability of FilterV to larger graphs. Therefore, we further develop a novel verification-free (VFree) approach by leveraging the advanced dynamic counting structure proposed. Theoretically, we prove that VFree can reduce the cost of each valid candidate set computation in FilterV by a factor of O(|V|). Furthermore, VFree can avoid the explicit maximality verification because of the developed search paradigm. Finally, comprehensive experiments on 15 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques and model.

Attributed bipartite graphs (ABGs) are an expressive data model for describing the interactions between two sets of heterogeneous nodes that are associated with rich attributes, such as customer-product purchase networks and author-paper authorship graphs. Partitioning the target node set in such graphs into k disjoint clusters (referred to as k-ABGC) finds widespread use in various domains, including social network analysis, recommendation systems, information retrieval, and bioinformatics. However, the majority of existing solutions towards k-ABGC either overlook attribute information or fail to capture bipartite graph structures accurately, engendering severely compromised result quality. The severity of these issues is accentuated in real ABGs, which often encompass millions of nodes and a sheer volume of attribute data, rendering effective k-ABGC over such graphs highly challenging. In this paper, we propose TPO, an effective and efficient approach to k-ABGC that achieves superb clustering performance on multiple real datasets. TPO obtains high clustering quality through two major contributions: (i) a novel formulation and transformation of the k-ABGC problem based on multi-scale attribute affinity specialized for capturing attribute affinities between nodes with the consideration of their multi-hop connections in ABGs, and (ii) a highly efficient solver that includes a suite of carefully-crafted optimizations for sidestepping explicit affinity matrix construction and facilitating faster convergence. Extensive experiments, comparing TPO against 19 baselines over 5 real ABGs, showcase the superior clustering quality of TPO measured against ground-truth labels. Moreover, compared to the state of the arts, TPO is often more than 40x faster over both small and large ABGs., Comment: The technical report for the paper was accepted to KDD 2024. 14 pages

Let G be a finite simple graph and let indm(G) and ordm(G) denote the induced matching number and the ordered matching number of G, respectively. We characterize all bipartite graphs G with indm(G) = ordm(G). We establish the Castelnuovo-Mumford regularity of powers of edge ideals and depth of powers of cover ideals for such graphs. We also give formulas for the count of connected non-isomorphic spanning subgraphs of the complete bipartite graph K_{m,n} for which indm(G) = ordm(G) = 2, with an explicit expression for the count when m = 2,3,4 and m <= n.

Given a graph $T$ and a family of graphs $\mathcal{F}$, the maximum number of copies of $T$ in an $\mathcal{F}$-free graph on $n$ vertices is called the generalized Tur\'{a}n number, denoted by $ex(n, T , \mathcal{F})$. When $T= K_2$, it reduces to the classical Tur\'{a}n number $ex(n, \mathcal{F})$. Let $ex_{bip}(b,n, T , \mathcal{F})$ be the maximum number of copies of $T$ in an $\mathcal{F}$-free bipartite graph with two parts of sizes $b$ and $n$, respectively. Let $P_k$ be the path on $k$ vertices, $\mathcal{C}_{\ge k}$ be the family of all cycles with length at least $k$ and $M_k$ be a matching with $k$ edges. In this article, we determine $ex_{bip}(b,n, K_{s,t}, \mathcal{C}_{\ge 2n-2k})$ exactly in a connected bipartite graph $G$ with minimum degree $\delta(G) \geq r\ge 1$, for $b\ge n\ge 2k+2r$ and $k\in \mathbb{Z}$, which generalizes a theorem of Moon and Moser, a theorem of Jackson and gives an affirmative evidence supporting a conjecture of Adamus and Adamus. As corollaries of our main result, we determine $ex_{bip}(b,n, K_{s,t}, P_{2n-2k})$ and $ex_{bip}(b,n, K_{s,t}, M_{n-k})$ exactly in a connected bipartite graph $G$ with minimum degree $\delta(G) \geq r\ge 1$, which generalizes a theorem of Wang. Moreover, we determine $ex(n, K_{s,t}, \mathcal{C}_{\ge k})$ and $ex(n, K_{s,t}, P_{k})$ respectively in a connected graph $G$ with minimum degree $\delta(G) \geq r\ge 1$, which generalizes a theorem of Lu, Yuan and Zhang., Comment: 19 pages