qpUpdateCliquesRemoving {qpgraph} | R Documentation

## Update clique list when removing one edge

### Description

Updates the set of (maximal) cliques of a given undirected graph when removing one edge.

### Usage

    qpUpdateCliquesRemoving(g, clqlst, v, w, verbose=TRUE)

### Arguments

`g` | either a `graphNEL` object or an adjacency matrix of the given undirected graph.
`clqlst` | list of cliques of the graph encoded in g. this list should start on element n+1 (for n vertices) while between elements 1 to n there should be references to the cliques to which each of the 1 to n vertices belong to (i.e., the output of `qpGetCliques`) with parameter `clqspervtx=TRUE`.
`v` | vertex of the edge being removed.
`w` | vertex of the edge being removed.
`verbose` | show progress on calculations.

### Details

To find the list of all (maximal) cliques in an undirected graph is an NP-hard problem which means that its computational cost is bounded by an exponential running time (Garey and Johnson, 1979). For this reason, this is an extremely time and memory consuming computation for large dense graphs. If we spend the time to obtain one such list of cliques and we remove one edge of the graph with this function we may be able to update the set of maximal cliques instead of having to generate it again entirely with `qpGetCliques` but it requires that in the first call to `qpGetCliques` we set `clqspervtx=TRUE`. It calls a C implementation of the algorithm from Stix (2004).

### Value

The updated list of maximal cliques after removing one edge from the input graph. Note that because the corresponding input clique list had to be generated with the argument `clqspervtx=TRUE` in the call to `qpGetCliques`, the resulting updated list of cliques also includes in its first p entries (p=number of variables) the indices of the cliques where that particular vertex belongs to. Notice also that although this strategy might be in general more efficient than generating again the entire list of cliques, when removing one edge from the graph, the clique enumeration problem remains NP-hard (see Garey and Johnson, 1979) and therefore depending on the input graph its computation may become unfeasible.

### Author(s)

R. Castelo

### References

Garey, M.R. and Johnson D.S. Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Francisco, 1979.

Stix, V. Finding all maximal cliques in dynamic graphs Comput. Optimization and Appl., 27:173-186, 2004.

### See Also

`qpCliqueNumber` `qpGetCliques` `qpIPF`

### Examples

    ## the example below takes about 30 seconds to execute and for that reason
    ## it is not executed by default
    ## Not run:
    require(graph)

    set.seed(123)
    nVar <- 1000
    g1 <- randomEGraph(V=as.character(1:nVar), p=0.1)
    g1
    clqs1 <- qpGetCliques(g1, clqspervtx=TRUE, verbose=FALSE)

    length(clqs1)

    g2 <- removeEdge(from="1", to=edges(g1)[["1"]][1], g1)
    g2

    system.time(clqs2a <- qpGetCliques(g2, verbose=FALSE))

    system.time(clqs2b <- qpUpdateCliquesRemoving(g1, clqs1, "1", edges(g1)[["1"]][1], verbose=FALSE))

    length(clqs2a)

    length(clqs2b)-nVar

    ## End(Not run)

[Package qpgraph version 2.16.0 Index]