Palestinian president Mahmoud Abbas has threatened to break off a unity agreement with Hamas.
The threat comes if the Islamist movement does not allow the government to operate properly in Gaza.
Mr Abbas said: "We won't accept a partnership with (Hamas) if the situation continues like this in Gaza where there is a shadow government of 27 deputy ministers who are running the territory,"
Mr Abbas was speaking on his arrival in Cairo late last night.
He said the national consensus government cannot do anything on the ground.
Under the terms of a reconciliation deal signed in April, the Palestinians agreed to form an interim consensus government of technocrats, ending seven years of rival administrations in the West Bank and Gaza.
The unity deal sought to end years of bitter and sometimes bloody rivalry between the Islamist Hamas movement and its Fatah rivals who dominate the West Bank-based Palestinian Authority.
The new cabinet, which is based in Ramallah, took office on 2 June with Gaza's Hamas government officially stepping down the same day.
Despite the handover, Hamas has remained the de facto power in Gaza.
The implementation of provisions of the unity agreement were put on hold due to the violence which erupted in earnest on 8 July.