On the maximum fraction of edges covered by tt perfect matchings in a cubic bridgeless graph

A conjecture of Berge and Fulkerson (1971) states that every cubic bridgeless graph contains 6 perfect matchings covering each edge precisely twice, which easily implies that every cubic bridgeless graph has three perfect matchings with empty intersection (this weaker statement was conjectured by Fan and Raspaud in 1994). Let mtmt be the supremum of all reals α≤1α≤1 such that for every cubic bridgeless graph GG, there exist tt perfect matchings of GG covering a fraction of at least αα of the edges of GG. It is known that the Berge–Fulkerson conjecture is equivalent to the statement that m5=1m5=1, and implies that m4=1415 and m3=45. In the first part of this paper, we show that m4=1415 implies m3=45, and m3=45 implies the Fan–Raspaud conjecture, strengthening a recent result of Tang, Zhang, and Zhu. In the second part of the paper, we prove that for any 2≤t≤42≤t≤4 and for any real ττ lying in some appropriate interval, deciding whether a fraction of more than (resp. at least) ττ of the edges of a given cubic bridgeless graph can be covered by tt perfect matching is an NP-complete problem. This resolves a conjecture of Tang, Zhang, and Zhu.