{"id":773,"date":"2014-11-20T14:25:56","date_gmt":"2014-11-20T14:25:56","guid":{"rendered":"http:\/\/corner.mimuw.edu.pl\/?p=773"},"modified":"2018-09-12T08:45:12","modified_gmt":"2018-09-12T08:45:12","slug":"graph-isomorphism-on-graphs-of-bounded-treewidth","status":"publish","type":"post","link":"https:\/\/corner.mimuw.edu.pl\/?p=773","title":{"rendered":"Graph Isomorphism on graphs of bounded treewidth"},"content":{"rendered":"<p>The Graph Isomorphism problem is interesting for many reasons, one being the fact that its complexity status is still unclear - it is probably not NP-complete, but not known to be in P either. In the past decades, researchers identified a large number of special graph classes for which GI is polynomial-time solvable, including <a href=\"http:\/\/dx.doi.org\/10.1145\/800119.803896\" target=\"_blank\" rel=\"noopener\">planar graphs<\/a>, <a href=\"http:\/\/dx.doi.org\/10.1016\/0022-0000(82)90009-5\" target=\"_blank\" rel=\"noopener\">graphs of bounded maximum degree<\/a>, and <a href=\"http:\/\/dx.doi.org\/10.1007\/BF01098279\" target=\"_blank\" rel=\"noopener\">graphs excluding a fixed minor<\/a>, among others.<\/p>\n<p>A closer look at the known algorithms for graphs of bounded degree or graphs excluding a fixed minor reveals that the dependency in the running time bound on the \"forbidden pattern\" is quite bad: <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_84af0f59ee6123de2952346a4d40c97c.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in the first case or <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f29ff31c51669e2c18333e0ebf3278fd.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in the second case, for some function <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8fa14cdd754f91cc6554c9e71929cce7.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Seeing such dependencies, a natural question is: do there exist fixed-parameter algorithms, parameterized by the \"forbidden pattern\"? In other words, does the exponent in the polynomial factor in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> need to depend on the pattern, on can we obtain an algorithm with running time <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_cea6e4e15d792fb1b5b7a80e5dfc880e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>?<\/p>\n<p>This question remains widely open for all aforementioned cases of bounded degree or excluded minor. In our recent FOCS 2014 paper, we have answered the question affirmatively for the special case of bounded treewidth graphs, proving that isomorphism of two <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>-vertex graphs of treewidth <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> can be tested in time <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2b2c730b022a389f3218da6f93d1a3e4.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>As a starting point, observe that comparing (testing isomorphism) of two graphs <em>together with their given tree decompositions<\/em> (that is, we want to check if the whole structures consisting of a graph and its decomposition are isomorphic) can be done easily in time polynomial in the size of the graphs, and exponential in the width of the decompositions. This is a relatively standard, but tedious, exercise from the area of designing dynamic programming algorithms on tree decompositions: if you have seen a few of these, I guess you can figure out the details, but if you don't, this is probably one of the worst examples to start with, so just assume it can be done. Alternatively, you may use the <a href=\"http:\/\/arxiv.org\/abs\/1403.7238\" target=\"_blank\" rel=\"noopener\">recent results of Otachi and Schweitzer<\/a> that say that one needs only a set of bags for the decomposition, even without the structure of the decomposition tree itself.<\/p>\n<p>With this observation, the task of comparing two bounded-treewidth graphs reduces to the following: given a graph <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of treewidth <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, we would like to compute <em>in an isomorphic-invariant way<\/em> a tree decomposition of $G$ of near-optimal width. Here, isomorphic-invariant means that we do not want to make any decisions depending on the representation of the graph in the memory (like, \"take arbitrary vertex\"), and the output decomposition should be the same (isomorphic) for isomorphic input graphs. Given such an isomorphic-invariant treewidth approximation algorithm, we can now compute the decompositions of both input graphs, and compare given pairs (graph, its tree decomposition), as described in the previous paragraph. Note that for this approach we do not need to output exactly <em>one<\/em> tree decomposition; we can output, say, <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_6595d679e306a127a3fe53268bcaddb2.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of them, and compare every pair of decompositions for two input graphs for the Graph Isomorphism problem; we only need that the set of output decompositions is isomorphic invariant.<\/p>\n<p>To cope with this new task, let us look at the known treewidth approximation algorithms; in particular, the arguably simplest one - the Robertson-Seymour algorithm. This algorithm provides a constant approximation in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_97b38e2715299ea8ea615ab198f9d49b.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> time, where <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is the treewidth of the input <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b8b965ad4bca0e41ab51de7b31363a1.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>-vertex graph <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. It is a recursive procedure that decomposes a part <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_ac06b9575db35aa5ff8e39d142ef7853.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of the input graph, given a requirement that a set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8c3c18c12cf4f73b60f4fdecf70f8b8e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> should be contained in the top bag of the output decomposition. Think of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> as an interface to the rest of the graph; we will always have <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7c2cca421662a0e24be17af2d50f858f.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, but for technical reasons the set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> could be larger. During the course of the algorithm we maintain an invariant <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_3828a24d94e34f535d6ed597e9b159bd.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>In the leaves of the recursion we have <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_711277f7e8a6d2c641613530bb03b4e0.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and we output a single bag <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7fc56270e7a70fa81a5935b72eacbe29.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. If <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is small, say, <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_22639dd7f59ce8384b407fda9424b6d3.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, then we can add an arbitrary vertex to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and recurse. The interesting things happen when <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> grows beyond the threshold <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_12277132c4446ec03bdb8b55891b24d4.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>As the graph is of treewidth <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, but <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_c10f852f926fc560b520d11d20973451.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, in an optimal decomposition of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> the set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is spread across many bags. A simple argument shows that there exists a bag <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_02129bb861061d1a052c592e2dc6b383.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dd8b4f1f2e798489cd3c23e410bfbf6d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, such that every component of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_80fdd026ff4ff450e82352a436e7c143.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> contains at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5cb0f9775e986646011ccb676a59ac3d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> vertices of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. The algorithm takes <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_062c5b3bfce8b45e513529100b8937a2.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> as a root bag (note that <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_615c84fd46e528d8cfc7c3ea12a1af54.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>), and recurses on every connected component of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7527faf06a5983dce3211d5dd0125463.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>; formally, for every connected component <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7527faf06a5983dce3211d5dd0125463.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, we recurse on <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e2db87db60075112178081a78862a57f.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> with <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_a2215ba8a4b1617fbefa330229802263.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Since every component of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_80fdd026ff4ff450e82352a436e7c143.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> contains at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5cb0f9775e986646011ccb676a59ac3d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> vertices of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, in every recursive call the new set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is of size at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_62a26c6569e38cbe0c003386502b86df.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>In the above algorithm, there are two steps that are very deeply not isomorphic-invariant: \"take an arbitrary vertex to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>\" in the case of small <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and \"take any such <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_02129bb861061d1a052c592e2dc6b383.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>\" in the case of large <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. We start fixing the algorithm in the second, more interesting case.<\/p>\n<p>Before we start, let us think how we can find such a set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_02129bb861061d1a052c592e2dc6b383.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> - the argument provided two paragraphs ago only asserted its existence. One of the ways to do it is to iterate through all disjoint sets <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_29f1b33652e023d8445e0bcff466d272.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of size exactly <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9276045de13b49323df13884fbab39e2.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> each, and check if the minimum separator between <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f09564c9ca56850d4cd6b3319e541aee.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_ac06b9575db35aa5ff8e39d142ef7853.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is of size at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_a31a860e7a59c7616c1515ec3ae652a6.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> (such a separator can contain vertices of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> or <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f09564c9ca56850d4cd6b3319e541aee.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, these are deletable as well). If such a separator is found, it is a good candidate for the set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_02129bb861061d1a052c592e2dc6b383.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> - it does not necessarily have the property that every connected component of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_80fdd026ff4ff450e82352a436e7c143.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> contains at most half of the vertices of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, but the claim that in the recursive calls the size of the set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> decreased is still true. Of course, in this approach we have two not isomorphic-invariant choices: the choice of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f09564c9ca56850d4cd6b3319e541aee.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and the choice of the minimum separator <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_02129bb861061d1a052c592e2dc6b383.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>Luckily, an (almost) isomorphic-invariant way to make the second choice has already been well understood: by submodularity of cuts, there exists a well-defined notion of the minimum cut closest to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and the one closest to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f09564c9ca56850d4cd6b3319e541aee.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. But how about the choice of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f09564c9ca56850d4cd6b3319e541aee.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>?<\/p>\n<p>The surprising answer is: it works just fine if we just throw into the constructed bag <em>all<\/em> separators for <em>every choice<\/em> of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f09564c9ca56850d4cd6b3319e541aee.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. That is, we start with the tentative bag <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_cb3cd91e9eb88b3372f735ad3d81ffff.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, we iterate over all such (ordered) pairs <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_def5fe54174a34dd4b98d05e4731631d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and throw into the constructed bag <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> the minimum cut between <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_f09564c9ca56850d4cd6b3319e541aee.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that is closest to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, as long as it has size at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_a31a860e7a59c7616c1515ec3ae652a6.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. We recurse on all connected components of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0db4ae8426a59c63c76a26acb16e48a4.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> as before; the surprising fact is that the sizes of the sets <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in the recursive calls did not grow. To prove this fact, we analyse what happens to the components of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0db4ae8426a59c63c76a26acb16e48a4.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> when you add <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b97edadcc4a496d9318680db97d357ed.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> cuts one-by-one; a single step of this induction turns out to be an elementary application of submodularity. Furthermore, note that if the size of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is bounded in terms of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, so is the set of the bag <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>: <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_a37be3843938edd25ece91f9400e9bde.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>Having made isomorphic-invariant the \"more interesting\" case of the Robertson-Seymour approximation algorithm, let us briefly discuss the case of the small set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>: we need to develop an isomorphic-invariant way to grow this set. Here, we need some preprocessing: by known tricks, we can assume that (a) the input graph does not contain any clique separators, and (b) if <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8a757a25b1cb102a08bd29b42e24a521.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, then the minimum cut between <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b774effe4a349c6dd82ad4f4f21d34c.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9e3669d19b675bd57058fd4664205d2a.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is of size at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Furthermore, observe that in our algorithm, contrary to the original Robertson-Seymour algorithm, we always maintain the invariant that <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2fd2c123f534a454d5825be044cda8a8.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_6f6084e965167fe4e7a2a61c0df9a486.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is connected. Thus, <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is never a clique in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and, if <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_22639dd7f59ce8384b407fda9424b6d3.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, we can throw into a bag the minimum cut between <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b774effe4a349c6dd82ad4f4f21d34c.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9e3669d19b675bd57058fd4664205d2a.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that is closest to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7b774effe4a349c6dd82ad4f4f21d34c.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, for every ordered pair <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9093cc72d2d40694b9361424cb0a6803.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> where <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_ba61d3a4ec6be3a7f51fceb6ca1aaa93.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8a757a25b1cb102a08bd29b42e24a521.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>In this way, the lack of clique separators ensures that we always make a progress in the algorithm, by \"eating\" at least one vertex of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ee1bd3d3949bf3f5c715e07d5e85362.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. The bound on the size of minimum cut between two nonadjacent vertices ensures that the bag created in this way is of size <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_3c3e7b91cce026230299d545a8b418a8.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and so are the sets <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in the recursive calls. Consequently, our algorithm computes in an isomorphic-invariant way a tree decomposition with adhesions of size <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_3c3e7b91cce026230299d545a8b418a8.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and bags of size <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_a22ce035c09370799f0d3cef228e444a.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>Well, there is one small catch - neither of the aforementioned steps is good to <em>start<\/em> the algorithm, to provide the initial call of the recursion; the Robertson-Seymour approximation starts with just <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7924272e49b34a8f0710bfea22eed8a3.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_990eaade04f552f02af411ebca2b5000.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Here, we can start with <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7924272e49b34a8f0710bfea22eed8a3.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0fad7c8cc3dd02aadfa7f9a7be6c0b12.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> for every pair <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_926213d74764024ed0897fd575c3bb58.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of nonadjacent vertices, as in this call the step with the small set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_5dbc98dcc983a70728bd082d1a47546e.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> will work fine. But this produces not a single isomorphic-invariant tree decomposition, but a family of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9f84a66d88d24c3b1bc91df5b5346a13.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> decompositions - which is still fine for the isomorphism test.<\/p>\n<p>A cautious reader would also notice that the described algorithm results in a double-exponential dependency on the parameter <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in the running time, contrary to the claim of the <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e4be24de46472f32ce999db26f2f161d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> term. Getting down to this dependency requires a bit more technical work; we refer to <a href=\"http:\/\/arxiv.org\/abs\/1404.0818\">the full version of our paper<\/a> for details.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Graph Isomorphism problem is interesting for many reasons, one being the fact that its complexity status is still unclear - it is probably not NP-complete, but not known to be in P either. In the past decades, researchers identified &hellip; <a href=\"https:\/\/corner.mimuw.edu.pl\/?p=773\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":5,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[17,16],"tags":[],"_links":{"self":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/773"}],"collection":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=773"}],"version-history":[{"count":8,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/773\/revisions"}],"predecessor-version":[{"id":988,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/773\/revisions\/988"}],"wp:attachment":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=773"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=773"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}