Balanced Substructures in Bicolored Graphs

An edge-colored graph is said to be balanced if it has an equal number of edges of each color. Given a graph G whose edges are colored using two colors and a positive integer k, the objective in the EDGE BALANCED CONNECTED SUBGRAPH problem is to determine if G has a balanced connected subgraph containing at least k edges. We first show that this problem is NP-complete and remains so even if the solution is required to be a tree or a path. Then, we focus on the parameterized complexity of EDGE BALANCED CONNECTED SUBGRAPH and its variants (where the balanced subgraph is required to be a path/tree) with respect to k as the parameter. Towards this, we show that if a graph has a balanced connected subgraph/tree/path of size at least k, then it has one of size at least k and at most f(k) where f is a linear function. We use this result combined with dynamic programming algorithms based on color coding and representative sets to show that EDGE BALANCED CONNECTED SUBGRAPH and its variants are FPT. Further, using polynomial-time reductions to the MULTILINEAR MONOMIAL DETECTION problem, we give faster randomized FPT algorithms for the problems. In order to describe these reductions, we define a combinatorial object called relaxed-subgraph. We define this object in such a way that balanced connected subgraphs, trees and paths are relaxed-subgraphs with certain properties. This object is defined in the spirit of branching walks known for the STEINER TREE problem and may be of independent interest.