The Afghan Defense ministry in Kabul said at least 20 Taliban guerrillas were killed in a NATO air strike in a village in Arghandab, while 16 fighters were killed in Khohak, also in Arghandab. Two Afghan soldiers also were killed, the ministry said in a statement.
A top provincial official in Kandahar, Ahmed Wali Karzai, the brother of Afghan President Hamid Karzai, said hundreds of families had fled to the city to avoid the fighting, the Associated Press reported.
Many of the insurgents are suspected to be part of a group of some 400 Taliban prisoners who broke out of jail in Kandahar after a bomb blast last week.
Afghanistan's government on Tuesday claimed that between 300 and 400 militant fighters were operating in Arghandab, some 12 miles from Kandahar city.
Canadian military officials who patrolled through Arghandab over the last day reported "no obvious signs" of insurgent activity, the AP reported. Pentagon officials said reports of hundreds of Taliban in Arghandab were being overstated.
"The operation is proceeding to schedule. We have no evidence of hundreds of Taliban," Mark Laity, a spokesman for NATO in Kabul, said, according to the New York Times. "We have got substantial forces there, and we are prepared for any eventuality."
Afghan and NATO troops are now expected to go from village to village to try and flush out the Taliban. In addition, security is expected to be tightened in Kandahar and a night curfew is expected to take effect soon.
The Taliban have long sought to control Arghandab, which also offers good fighting positions its pomegranate and grape groves. If they were to secure control of the region, militants could launch attacks into the city of Kandahar, The Taliban's former spiritual home.
Mohammad Faiz, who had evacuated his family from an outlying village earlier this week, told the AP that he was hoping he could return to his home to retrieve his belongings.
"I have come to see if I can take away our house items," he told reporters at the head of Arghandab valley. He watched as trucks carrying Afghan and NATO soldiers drove by and down into the valley.
The Afghan defense ministry told news services that as many as eight villages had been taken by Taliban and that villagers fleeing the area had reported that the guerillas had buried land mines in the surrounding area in an attempt to hold off NATO and Afghan troops.
Meanwhile, the British Ministry of Defense said four British soldiers were killed when an explosive was detonated against their vehicle during a patrol in neighboring Helmand province on Tuesday. At least one soldier was wounded. The incident came just days after Prime Minister Gordon Brown promised to send more British troops to the region.