{"id":35406,"date":"2019-10-31T22:04:08","date_gmt":"2019-10-31T19:04:08","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov\/"},"modified":"2021-01-02T13:01:41","modified_gmt":"2021-01-02T11:01:41","slug":"kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"How to Solve NP-Hard Problems Using Parameterized Algorithms","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Scientific research work is perhaps the most interesting part of our education. The idea is to try yourself in your chosen field while still at university. For example, students in Software Engineering and Machine Learning often undertake research projects in companies (primarily JetBrains or Yandex, but not only).<\/p>\n

In this post, I will talk about my project in the field of Computer Science. As part of this work, I studied and implemented approaches to solving one of the most well-known NP-hard problems: the vertex cover problem<\/b>.<\/p>\n

Currently, there is a rapidly developing approach to NP-hard problems \u2014 parameterized algorithms. I will try to bring you up to speed, share a few simple parameterized algorithms, and describe one powerful method that has helped me significantly. I presented my results at the PACE Challenge competition: after the open tests, my solution ranks third, and the final results will be known on July 1.<\/p>\n

\"How
\n<\/a><\/noindex><\/p>\n

About Me<\/h3>\n

My name is Vasily Alfyorov, and I am currently finishing my third year at HSE \u2014 St. Petersburg. I have been interested in algorithms since my school days when I studied at Moscow School 179 and successfully participated in informatics Olympiads.<\/p>\n

A finite number of specialists in parameterized algorithms walk into a bar\u2026<\/h3>\n

The example is taken from the book \u2018Parameterized Algorithms\u2019<\/a><\/noindex><\/i><\/p>\n

Imagine you are a bouncer at a bar in a small town. Every Friday, half the town comes to your bar to relax, which gives you quite a bit of trouble: you need to eject rowdy patrons to prevent fights. Eventually, you get tired of this and decide to take preventive measures.<\/p>\n

Since your town is small, you know exactly which pairs of patrons are likely to get into a fight if they end up in the bar together. You have a list of n<\/i> people who will come to the bar tonight. You decide not to let in certain townsfolk in such a way that no one ends up fighting. At the same time, your superiors do not want to lose profits and will be unhappy if you do not let in more than k<\/i> people.<\/p>\n

Unfortunately, the problem you face is a classic NP-hard problem. You may know it as Vertex Cover<\/a><\/noindex>, or how to approach the vertex cover problem. For such problems, there are generally no algorithms that work in a reasonable time frame. To be precise, the unproven but quite strong ETH (Exponential Time Hypothesis) suggests that this problem cannot be solved in a reasonable time \"How, meaning that nothing significantly better than brute force can be devised. For instance, suppose a group of n = 1000<\/i> people is planning to come to your bar. Then brute force would lead to \"How combinations, which amounts to approximately \"How \u2014 an enormous number. Fortunately, your management has imposed a restriction of k = 10<\/i>, so the number of combinations you need to consider is much smaller: the number of subsets of ten elements is \"How. This is an improvement, but still not something that can be counted in a day even on a powerful cluster.
\n\"How
\nTo avoid the likelihood of fights in such a configuration of strained relations among bar patrons, you need to exclude Bob, Daniel, and Fyodor. There is no solution where only two are left out.<\/p>\n

Does this mean it's time to give up and let everyone in? Let's consider other options. For example, you might choose not to admit only those who are likely to fight with a very large number of people. If someone could fight with at least k + 1<\/i> other individuals, then they definitely shouldn't be allowed in\u2014otherwise, you'll have to keep out all k + 1<\/i> the locals they could fight with, which would certainly upset management.<\/p>\n

Suppose you have excluded everyone you could based on this principle. Then all remaining individuals can fight with at most k<\/i> people. By excluding k<\/i> individuals, you can prevent at most \"How conflicts. Thus, if more than \"How people are involved in at least one conflict, you definitely won't be able to prevent them all. Since, of course, entirely non-conflictual individuals must be allowed in, you need to consider all ten-person subsets among two hundred people. There are approximately \"How, and that number of operations can already be handled on a cluster.<\/p>\n

If it's safe to let in completely non-conflicting individuals, what about those who are involved in just one conflict? In fact, they can also be admitted, closing the door to their opponent. Indeed, if Alice is only in conflict with Bob, letting in Alice from the two means we won't lose: Bob may have other conflicts, and Alice definitely has none. Besides, it makes no sense to not let both in. After such operations, there remain no more \"How guests with unresolved fates: we have a total of \"How conflicts, each with two participants and each involved in at least two. Therefore, we only need to consider a mere \"How options, which can easily be counted in half a day on a laptop.<\/p>\n

In fact, simple reasoning can lead to even more appealing conditions. Notice that we necessarily need to resolve all disputes, that is, from each conflicting pair, we must choose at least one person not to let in. Let's consider such an algorithm: take any conflict, remove one participant and recursively launch from the remainder, then remove the other and also recursively launch. Since we are throwing someone out at each step, the recursion tree of this algorithm is a binary tree of depth k<\/i>, hence the total algorithm operates in \"How, where n<\/i> \u2014 the number of vertices, while m<\/i> \u2014 the number of edges. In our example, this amounts to around ten million, which can be calculated in mere fractions of a second, not only on a laptop but even on a mobile phone.<\/p>\n

The example provided above is an example of parameterized algorithms<\/b>. Parameterized algorithms are algorithms that operate in time f(k) poly(n)<\/i>, where p<\/i> \u2014 a polynomial, f<\/i> \u2014 an arbitrary computable function, and k<\/i> \u2014 some parameter that, quite possibly, will be much smaller than the size of the task.<\/p>\n

All reasoning prior to this algorithm leads to an example of kernelization<\/b> \u2014 one of the common techniques for creating parameterized algorithms. Kernelization is the process of reducing the size of a problem to a value bounded by a function of a parameter. The resulting problem is often called a kernel. For example, through simple reasoning about the degrees of vertices, we obtained a quadratic kernel for the Vertex Cover problem, parameterized by the size of the solution. There are other parameters that can be chosen for this problem (for instance, Vertex Cover Above LP), but we will specifically discuss this parameter.<\/p>\n

Pace Challenge<\/h3>\n

Competition PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) was established in 2015 to create a link between parameterized algorithms and practical approaches used to solve computational problems. The first three competitions were dedicated to finding graph treewidth (Treewidth<\/a><\/noindex>), finding the Steiner tree (Steiner Tree<\/a><\/noindex>), and finding a set of vertices that cuts cycles (Feedback Vertex Set<\/a><\/noindex>). This year, one of the problems where participants could test their skills was the aforementioned vertex cover problem.<\/p>\n

The competition is gaining popularity each year. According to preliminary data, this year, 24 teams participated in the competition to solve the vertex cover problem alone. It is worth noting that the competition lasts not just a few hours, or even a week, but several months. Teams have the opportunity to study the literature, come up with their own original idea, and attempt to implement it. Essentially, this competition represents research work. The ideas for the most effective solutions and the awarding of winners will take place in conjunction with the IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) as part of the largest annual algorithmic gathering in Europe ALGO<\/a><\/noindex>. More detailed information about the competition can be found at the website<\/a><\/noindex>, while past years' results are available at here<\/a><\/noindex>.<\/p>\n

Solution Scheme<\/h3>\n

To tackle the vertex cover problem, I tried to apply parameterized algorithms. They generally consist of two parts: simplification rules (which ideally lead to kernelization) and splitting rules. Simplification rules are a preprocessing step that takes polynomial time. The goal of applying such rules is to reduce the problem to an equivalent one of smaller size. The simplification rules are the most costly part of the algorithm, and applying this part leads to an overall runtime instead of just plain polynomial time. \"How In our case, the splitting rules are based on the fact that for each vertex, we must answer either with it or one of its neighbors.<\/p>\n

The overall scheme is as follows: we apply the simplification rules, then we choose a vertex and make two recursive calls: in the first, we include it in the answer, and in the second, we include all its neighbors. This is referred to as splitting (branching) at this vertex.<\/p>\n

There will be exactly one addition to this scheme in the next paragraph.<\/p>\n

Ideas for splitting (branching) rules<\/h3>\n

Let's discuss how to choose a vertex for the splitting.
\nThe main idea is quite greedy in an algorithmic sense: let's take the vertex of maximum degree and split precisely at it. Why does this seem better? Because in the second branch of the recursive call, we thus eliminate a lot of vertices. One can expect that a small graph will remain, and we will process it quickly.<\/p>\n

This approach, when combined with the previously discussed simple kernelization techniques, performs decently and solves some tests with a few thousand vertices. However, for example, it performs poorly on cubic graphs (that is, graphs where the degree of each vertex is three).
\nThere is one more idea based on a fairly straightforward thought: if the graph is disconnected, the problem on its connected components can be solved independently, merging the answers at the end. This, by the way, is the small promised modification in the scheme that will significantly speed up the solution: previously, in such cases, we worked with the product of the times for counting the answers of the components, but now we will work with the sum. And to speed up the branching, we need to turn the connected graph into a disconnected one.<\/p>\n

How to do this? If there is an articulation point in the graph, you need to branch specifically at that point. An articulation point is a vertex that, when removed, causes the graph to become disconnected. You can find all the articulation points in the graph using a classic algorithm in linear time. This approach significantly speeds up branching.
\n\"How
\nRemoving any of the highlighted vertices will cause the graph to split into connected components.<\/p>\n

We will do this, but we want more. For example, to search for small vertex cuts in the graph and perform branching based on those vertices. The most efficient known method to find a minimum global vertex cut is to use the Gomory-Hu tree, which can be constructed in cubic time. In the PACE Challenge, the typical graph size is several thousand vertices. Under such circumstances, billions of operations are needed at each vertex of the recursion tree. This means that solving the problem within the allotted time is simply impossible.<\/p>\n

Let's try to optimize the solution. A minimum vertex cut between a pair of vertices can be found using any algorithm that constructs a maximum flow. We can apply Dinic's algorithm<\/a><\/noindex>, which works very quickly in practice. I suspect it can theoretically be shown to have a time complexity of \"How, which is already quite acceptable.<\/p>\n

I have tried several times to search for cuts between pairs of random vertices and take the most balanced one. Unfortunately, in the public tests of the PACE Challenge, this yielded poor results. I compared it with an algorithm that branched based on vertices with the highest degree, running them with a depth limit. After the algorithm attempted to find a cut this way, larger-sized graphs remained. This is because the cuts were very unbalanced: by removing 5-10 vertices, I was only able to detach 15-20.<\/p>\n

It's worth noting that in articles about theoretically the fastest algorithms, much more advanced techniques for selecting vertices for branching are used. These techniques have very complex implementations and often poor time and space estimates. I was unable to identify acceptable methods for practical use from them.<\/p>\n

How to apply simplification rules<\/h3>\n

We already have ideas for kernelization. Let me remind you:<\/p>\n

    \n
  1. If there is an isolated vertex, remove it.<\/li>\n
  2. If there is a vertex of degree 1, remove it and take its neighbor in the response.<\/li>\n
  3. If there is a vertex of degree at least k + 1<\/i>, include it in the response.<\/li>\n<\/ol>\n

    The first two are clear, but the third has a trick. If in the playful problem about the bar we were given an upper bound on k<\/i>, then in the PACE Challenge we simply need to find a vertex cover of minimal size. This is a typical transformation of search problems into decision problems, and often there is no distinction made between the two types of problems. In practice, when we write a solver for the vertex cover problem, the difference may matter. For example, as in the third point.<\/p>\n

    From an implementation perspective, there are two approaches. The first approach is called Iterative Deepening. It consists of starting with some reasonable lower bound on the answer, and then running our algorithm using this bound as an upper limit on the answer, not delving into recursion deeper than this bound. If we find an answer, it is guaranteed to be optimal; otherwise, we can increase this limit by one and run again.<\/p>\n

    The second approach is to keep some current optimal answer and search for a smaller answer, updating this parameter when found k<\/i> to cut off excess branches in the search.<\/p>\n

    After conducting several experiments overnight, I settled on a combination of these two methods: first, I run my algorithm with some depth limit on the search (choosing it so that it takes an insignificant time compared to the main solution) and use the best solution found as the upper limit on the answer \u2014 that is, on the very k<\/i>.<\/p>\n

    Vertices of degree 2<\/h3>\n

    We figured out vertices of degree 0 and 1. It turns out that this can also be done with vertices of degree 2, but it will require more complex operations on the graph.<\/p>\n

    To explain this, we need to denote the vertices in some way. Let's call a vertex of degree 2 vertex v<\/i>, and its neighbors \u2014 vertices x<\/i> and y<\/i>. Next, we will have two cases.<\/p>\n

      \n
    1. Once x<\/i> and y<\/i> \u2014 neighbors. Then we can include in the response x<\/i> and y<\/i>, and v<\/i> remove. Indeed, we need to take at least two vertices from this triangle in the response, and we definitely won't lose if we take x<\/i> and y<\/i>: they probably have other neighbors, while v<\/i> they do not.<\/li>\n
    2. Once x<\/i> and y<\/i> \u2014 not neighbors. Then it is stated that all three vertices can be merged into one. The idea is that in this case, there is an optimal solution, where we will take either v<\/i>, or both vertices x<\/i> and y<\/i>. Moreover, in the first case we will have to take all neighbors in the solution x<\/i> and y<\/i>, while in the second it is not necessary. This precisely corresponds to the cases when we do not take the merged vertex into the solution and when we do. It remains to note that in both cases the solution from such an operation decreases by one.<\/li>\n<\/ol>\n

      \"How<\/p>\n

      It is worth noting that this approach is quite difficult to implement neatly in a fair linear time. Merging vertices is a complex operation; you need to copy the lists of neighbors. If done carelessly, it can yield asymptotically suboptimal running time (for example, if after each merge many edges are copied). I stopped at searching for whole paths from vertices of degree 2 and analyzing a plethora of edge cases, such as cycles from these vertices or from all such vertices except one.<\/p>\n

      Additionally, this operation needs to be reversible so that when returning from recursion we restore the graph to its original state. To ensure this, I did not clear the edge lists of merged vertices, after which I simply knew which edges needed to be directed where. This implementation of graphs also requires carefulness but ensures fair linear time. And for graphs of several tens of thousands of edges, it fits easily into the processor cache, providing significant speed advantages.<\/p>\n

      Linear kernel<\/h3>\n

      Finally, the most interesting part of the kernel.<\/p>\n

      To begin with, let's recall that in bipartite graphs, the minimum vertex cover can be searched for \"How. For this, we need to use the Hopcroft-Karp<\/a><\/noindex> algorithm to find the maximum matching there, and then utilize the K\u00f6nig-Egervari<\/a><\/noindex>.<\/p>\n

      theorem. The idea of the linear kernel is as follows: first, we will split the graph, meaning instead of each vertex v<\/i> , we will create two vertices \"How and \"How, and instead of each edge u \u2014 v<\/i> , we will create two edges \"How and \"HowThe resulting graph will be bipartite. We will find the minimum vertex cover in it. Some vertices of the original graph will appear twice, some only once, and some not at all. The Nemhauser-Trotter theorem states that in this case, we can remove the vertices that did not appear at all and take as the answer those that appeared twice. Moreover, it says that from the remaining vertices (those that appeared once), we need to take at least half in the answer.<\/p>\n

      We have just learned to leave no more than 2k<\/i> vertices in the graph. Indeed, if the answer consists of at least half of all the vertices, then there are no more vertices than 2k<\/i>.<\/p>\n

      Here I managed to make a small step forward. It is clear that the core built in this way depends on which specific minimum vertex cover we have taken in the bipartite graph. I would like to take one such that the number of remaining vertices is minimized. Previously, this could only be done in time \"How. I have devised an implementation of this algorithm in time \"How, so this core can be searched in graphs with hundreds of thousands of vertices at each branching stage.<\/p>\n

      Result<\/h3>\n

      Practice shows that my solution works well on tests with several hundred vertices and several thousand edges. In such tests, it is quite reasonable to expect that a solution will be found within half an hour. The probability of finding an answer within an acceptable time generally increases if the graph has a sufficient number of high-degree vertices, for example, degree 10 and above.<\/p>\n

      To participate in the competition, the solutions had to be submitted to optil.io<\/a><\/noindex>. According to the presented table<\/a><\/noindex>, my solution ranks third among twenty in the open tests with a significant lead over the second place. To be completely honest, it is not entirely clear how solutions will be evaluated in the actual competition: for example, my solution passes fewer tests than the one in fourth place, but it works faster on the ones it does pass.<\/p>\n

      The results of the closed tests will be known on the first of July.<\/p>\n

      Source: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

      \u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u044b \u0441 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 Software Engineering \u0438 Machine Learning \u0447\u0430\u0441\u0442\u043e \u0438\u0434\u0443\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u041d\u0418\u0420\u044b \u0432 \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0438 (\u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c, JetBrains \u0438\u043b\u0438 \u042f\u043d\u0434\u0435\u043a\u0441, \u043d\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e). \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u0441\u0432\u043e\u0451\u043c \u043f\u0440\u043e\u0435\u043a\u0442\u0435 \u043f\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044e Computer Science. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":26562,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-35406","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47How to Solve NP-Hard Problems Using Parameterized Algorithms | ProHoster","description":"Research work is perhaps the most interesting part of our education. The idea is to try to immerse yourself in the chosen field while still at university.","canonical_url":"https:\/\/prohoster.info\/en\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041a\u0430\u043a \u0440\u0435\u0448\u0430\u0442\u044c NP-\u0442\u0440\u0443\u0434\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 | ProHoster","og:description":"\u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438.","og:url":"https:\/\/prohoster.info\/en\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:04:08+00:00","article:modified_time":"2021-01-02T11:01:41+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"35406","title":null,"description":"","keywords":"","keyphrases":null,"primary_term":null,"canonical_url":"","og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 23:06:35","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:03:22","updated":"2026-01-21 23:06:35","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}