You can use a maximum flow algorithm to compute the minimum cut between A and B in your graph.
Runtime: O(n*m) with an excess-scaling push-relabel variant (since you have only unit capacities).
Your solution is O(2^m * (n + m)) if you use DFS or BFS for reachability in the fixed subgraph.