It looks like the error appears only when a processor ends up with an empty edge list. That is, the following works with mpirun -np 1 but gives a segmentation fault with -np 2 using namespace boost; using boost::graph::distributed::mpi_process_group; typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS> Graph; typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> LocalMap; int nV = 30000; int num = 0; Graph G(nV); synchronize(G); std::vector<int> localComponent(nV); LocalMap components(localComponent.begin(),get(vertex_index, G)); add_edge(vertex(0,G),vertex(1,G),G); num = connected_components_ps(G, components); The following works with -np 2 as well (the only thing I did was adding an edge) int nV = 30000; int num = 0; Graph G(nV); synchronize(G); std::vector<int> localComponent(nV); LocalMap components(localComponent.begin(),get(vertex_index, G)); add_edge(vertex(0,G),vertex(1,G),G); add_edge(vertex(29998,G),vertex(29999,G),G); num = connected_components_ps(G, components); Unfortunately, in my application it is very likely that some processors end up with no edges. Is there a way to fix this other than adding fake edges from a vertex to itself? Thanks, Alessio