Bipartite graph reasoning GANs for person image generation by Tang, H, Bai, S, Torr, PHS, Sebe, N

“…We present a novel Bipartite Graph Reasoning GAN (BiGraphGAN) for the challenging person image generation task. …”

Bipartite graph reasoning GANs for person pose and facial image synthesis by Tang, H, Shao, L, Torr, PHS, Sebe, N

“…We present a novel bipartite graph reasoning Generative Adversarial Network (BiGraphGAN) for two challenging tasks: person pose and facial image synthesis. …”

A complexity trichotomy for approximately counting list H-colourings by Goldberg, L, Galanis, A, Jerrum, M

“…If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. …”

The Partner Units Problem − A Constraint Programming Case Study by Drescher, C

“…Technically it consists of partitioning a bipartite graph under side conditions. In this work we describe how constraint programming technology can be leveraged to tackle the problem. …”

A fixed-parameter perspective on #BIS by Curticapean, R, Dell, H, Fomin, F, Goldberg, L, Lapinskas, J

“…The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RHΠ1. …”

The complexity of approximately counting retractions by Focke, J, Goldberg, L, Zivny, S

“…The result is as follows: (1) Approximately counting retractions to a tree H is in FP if H is a star, a single looped vertex, or an edge with two loops. (2) Otherwise, if H is an irreflexive caterpillar or a partially bristled reflexive path, then approximately counting retractions to H is equivalent to approximately counting the independent sets of a bipartite graph — a problem which is complete in the approximate counting complexity class RHπ1. (3) Finally, if none of these hold, then approximately counting retractions to H is #P-complete under approximation-preserving reductions. …”

Counting subgraphs in somewhere dense graphs by Bressan, M, Goldberg, LA, Meeks, K, Roth, M

“…</li></ul> <p>These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting k-matchings in bipartite graphs (Curticapean, Marx; FOCS 14), in F-colourable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting k-independent sets in bipartite graphs (Curticapean et al.; Algorithmica 19).…”

Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems by Galanis, A, Goldberg, L, Yang, K

“…Our main result shows that: (i) if every function in Γ is affine, then #CSPΔ(Γ) is in FP for all Δ, (ii) otherwise, if every function in Γ is in a class called IM2, then for all sufficiently large Δ, #CSPΔ(Γ) is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Δ, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSPΔ(Γ), even within an exponential factor. …”

Fine-grained dichotomies for the Tutte plane and Boolean #CSP by Roth, M, Brand, C, Dell, H

“…The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time exp(o(n)) unless #ETH fails.…”

Approximately Counting Locally-Optimal Structures by Goldberg, L, Gysel, R, Lapinskas, J

“…Motivated by the difficulty of approximately counting maximal independent sets in bipartite graphs, we also study counting problems involving minimal separators and minimal edge separators (which are also locally-optimal structures). …”

Counting and finding homomorphisms is universal for parameterized complexity theory by Roth, M, Wellnitz, P

“…As a special case, we obtain an easy proof of the parameterized intractability result of the problem of counting k-matchings in bipartite graphs. …”