PMC:1481596 / 34996-36710 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1481596","sourcedb":"PMC","sourceid":"1481596","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1481596","text":"Reduction to the minimum vertex cover\nA square in a graph can be eliminated by adding one or both of its diagonals (chords) to the graph. For example, a graph in Figure 6 has two squares: (A, B, C, D) and (A, B, E, D). Note that (B, C, D, E) is not a square as one of its diagonals, (C, E), is an edge in the graph. The square (A, B, C, D) can be eliminated if either edge (A, C) or (B, D) is added to the graph. Furthermore, a single diagonal can eliminate more than one square. For example, the diagonal (B, D)eliminates both squares. We are interested in finding all minimal sets of diagonals of size up to k that eliminate all the squares in the graph.\nFigure 6 VC Reduction. A graph and a corresponding \"square coverage graph\". We reduce the above problem to the Minimum Vertex Cover problem. The squares in the original graph become edges and diagonals become vertices in the new graph. Thus the original graph is transformed to a \"square coverage\" graph, which in turn serves as an input to the Minimum Vertex Cover problem. In the Minimum Vertex Cover problem we are given a graph and are asked to find the smallest set of vertices that cover all the edges in the graph. An edge is covered if at least one of its end points is selected. Coming back to our example, it can be easily seen that {(B, D)} is the minimum vertex cover (Figure 6). Although the Minimum Vertex Cover problem is an NP-hard problem, if the size of the optimum solution is small an efficient algorithm can be obtained. In other words the Minimum Vertex Cover problem is fixed parameter tractable. We use an O(2k(n + m)) algorithm [26] to identify all minimal sets of edges of size up to k that eliminate all the squares in the graph.","divisions":[{"label":"title","span":{"begin":0,"end":37}},{"label":"p","span":{"begin":38,"end":656}},{"label":"figure","span":{"begin":657,"end":733}},{"label":"label","span":{"begin":657,"end":665}},{"label":"caption","span":{"begin":667,"end":733}},{"label":"p","span":{"begin":667,"end":733}}],"tracks":[]}