\nheuristics to get fast approximations. But what if we really need the true optimum? The other approach to making it faster, when you really want the true optimum, is parallelism: finding some way to subdivide
\nthe problem into smaller pieces which can be executed at the same time. This is obviously a limited
\ntechnique – you can’t stop the exponential growth in execution time by adding a specific finite
\nnumber of processors. But for particular problems, parallelism can make the difference between
\nbeing able to do something fast enough to be useful, and not being able to. For a non-graph
\ntheoretic but compelling example, there’s been work in something called microforecasting<\/em>, which is precise weather forecasting for extreme small areas. It’s useful for predicting things like severe lightning storms in local areas during events where there are large numbers of people. (For example, it was used at the Atlanta olympics.) Microforecasting inputs a huge amount of information about local conditions – temperature, air pressure, wind direction, wind velocity, humidity, and such, and computes a short-term forecast for that area. Microforecasting is completely useless if it takes longer to compute the forecast than it takes for the actual weather to develop. If you can find a way to split the computation among a hundred processors, and get a forecast in 5 minutes, you’ve got something really useful. If you have to run it on a single processor, and it takes 2 hours – well, by then, any storm
\nthat the forecast predicts is already over.<\/p>\n
For graphs, there’s a very natural way of decomposing problems for parallelization. Many complex graphs for real problems can be divided into a set of subgraphs, which can be handled in parallel. In
\nfact, this can happen on multiple levels: graphs can be divided into subgraphs, which can be divided
\ninto further subgraphs. But for now, we’ll mainly focus on doing it once – one decomposition of
\nthe graph into subgraphs for parallelization.<\/p>\n
<\/p>\n
For any graph, directed or undirected, we have a notion of connectedness<\/em>. A graph is Now, suppose we have a digraph which is connected, but not<\/em> strongly connected. Then The way that works is pretty simple. You find the strongly connected components, and contract each of For example, you can use this for graph coloring. Find the strongly connected components – and color those. Then you can merge the coloring results by doing a join of the strongly connected components, adding colors when necessary at the joints. <\/p>\n For example, look at the graph below. We can divide it into its strongly connected components, which I’ve \tmarked off by dotted lines.<\/p>\n Now, we can color each of the strongly connected components separately, producing the graph below.<\/p>\n Then we go back to the full graph – but we treat only look at the edges that join Doing it this way has two advantages. One is the fact that it’s so easily parallelizable: each of the strongly connected components can be colored simultaneously, and then The other advantage is that it’s actually a potential complexity reducer. That is, Next post, I’ll talk about algorithms for finding the strongly connected components: after all, using SCCs as a tool in this way only makes sense if we can find the SCCs quickly!<\/p>\n","protected":false},"excerpt":{"rendered":" One of the problems with many of the interesting graph algorithms is that they’re complex. As graphs get large, computations over them can become extremely slow. For example, graph coloring is NP-complete – so the time to run a true optimal graph coloring algorithm on an arbitrary graph grows exponentially in the size of the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[54],"tags":[],"class_list":["post-535","post","type-post","status-publish","format-standard","hentry","category-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-8D","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/535","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=535"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/535\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=535"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=535"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=535"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nconnected if, for any two vertices A and B in the graph, there’s a path between them. For directed
\ngraphs, we can define a closely related concept: strong connection. Two vertices v1<\/sub> and v2<\/sub> in a digraph are connected if\/f there’s a path between them – that is,
\nif there’s a path from v1<\/sub> to v2<\/sub>, and<\/em> there’s also a path
\nfrom v2<\/sub> to v1<\/sub>. The digraph is strongly connected<\/em> if and only if every pair of vertices in it are strongly connected.<\/p>\n
\none of the things we can do with that graph is look at ways of partitioning the graph into
\nstrongly-connected subgraphs. There are a bunch of reasons why doing that it useful: for example, there are many algorithms that can be implemented in a divide-and-conquer fashion by identifying the
\nstrongly connected components of the graph, performing the algorithm on those components, and then merging the results.<\/p>\n
\nthem to a single vertex. You end up with a new graph. You can compute properties of the graph by
\ndividing them into the strongly connected components – computing the things for each of the components, and them merging the results by using the contracted graph. If the graph is large enough, you can divide that contracted graph into its own strongly connected subgraphs.<\/p>\n![\"connected-components-pre.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_287.png?resize=470%2C308\")
<\/p>\n![\"particolor.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_288.png?resize=469%2C293\")
<\/p>\n
\nthe strongly connected components. And we re-shuffle colors to avoid conflicts where we’re joining subgraphs. When we can’t avoid a conflict by re-shuffling, we would add a color – but that isn’t necessary in this case. The end-result is shown below. <\/p>\n![\"fully-colored.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_289.png?resize=469%2C293\")
<\/p>\n
\nthe results merged. In terms of the common current models of parallel programming, this – like many other graph algorithms built using subdivision to strongly connected components – is a perfect candidate for implementation as a map-reduce.<\/a><\/p>\n
\ndoing this sequentially, finding a coloring for the strongly connected components and then merging, is an application of a useful heuristic that can, in general, speed up
\nthe graph coloring. In some cases, the merging of component colorings can be expensive enough to outweigh the savings of doing a group of smaller colorings, but
\nin general, for most graphs that appear in many real problems, the component coloring and merge is a faster way of finding the optimal coloring.<\/p>\n