Error in is_clique for graphs with multiple edges

[dcoudert]

The following graph is not a clique

sage: G = Graph(multiedges=True)
sage: G.add_cycle([0, 1, 2, 3])
sage: G.add_edge(0,1)
sage: G.add_edge(0,1)
sage: G.is_clique()
True

CC: @pelegm @jm58660 @fchapoton

Component: graph theory

Keywords: days94

Author: David Coudert

Branch/Commit: 50df10e

Reviewer: Jori Mäntysalo

Issue created by migration from https://trac.sagemath.org/ticket/25696

[dcoudert]

comment:1

There might be smarter way to do that, but at least it fix the issue

---

New commits:

80bbcda

trac #25696: fix issue with is_clique

[dcoudert]

Commit: 80bbcda

[dcoudert]

Branch: u/dcoudert/25696_is_clique

[pelegm]

comment:3

I'm not sure we have the right/common definition of cliques here. Docs say:

A clique is a set of vertices such that there is an edge between any two vertices.

I would say:

A clique is a set of vertices such that there is a single edge between any two vertices.

For example, according to this paper here,

A clique in a graph or multigraph G is a simple complete subgraph of G.

[pelegm]

Changed keywords from none to days94

[dcoudert]

comment:5

What we expect certainly depends on the context. One solution could be to add a parameter strict, such that when strict==True we want a simple complete subgraph, and when set to False, we may tolerate loops of multiple edges = contains a simple complete subgraph. This is certainly not perfect, I agree.

[sagetrac-git]

Changed commit from 80bbcda to 34d6cea

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

160e6b9	trac #25696: Merged with 8.3.beta8
34d6cea	trac #25696: add parameters induced and loops

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

de4e89c

trac #25696: fix failing doctest

[sagetrac-git]

Changed commit from 34d6cea to de4e89c

[dcoudert]

comment:8

I added parameter induced to check for an induced clique or if the graph contains a clique. I also added a parameter loops to deal with complete (di)graphs with loops. This way we have more flexibility, and we can get what we want.

The last commit exhibit a potential change of behavior when asking for an undirected clique inside a directed graph. I consider that we can have only 1 arc between a given pair of nodes to get an induced clique. Let me know if you agree.

[jm58660]

comment:10

The logic seems to be clear. However,

sage: g = Graph({1: [2]})
sage: g.is_clique([1,2,3])
True

Also the indentation in INPUT section for parameters vertices and directed_clique is wrong (but right for induced and loops).

[jm58660]

comment:11

Also

sage: g = Graph(3)
sage: g.is_clique([1,2,3])
False
sage: g = Graph(2)
sage: g.is_clique([1,2])
True

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

76fc46b	trac #25696: Merged with 8.3.rc0
50df10e	trac #25696: fix reviewers comments

[sagetrac-git]

Changed commit from de4e89c to 50df10e

[dcoudert]

comment:13

Good catch ! This is a side effect of g.subgraph(vertices) that don't check if vertices is a subset of the vertices of the graph. I added a simple test.

Do you think I should open a ticket to raise an error in g.subgraph(vertices) when some vertices (or edges) are not in the graph ?

[jm58660]

comment:14

Replying to @dcoudert:

Do you think I should open a ticket to raise an error in g.subgraph(vertices) when some vertices (or edges) are not in the graph ?

To me it sounds logical. I expect that

SymmetricGroup(2).subgroup((1,2), 'junk')
Poset({1: [2]}).subposet([1, 'junk'])
Graph({1:[2]}).subgraph([1, 'junk'])

gives similar output (they do not), and actually I have changed the output of

Poset({1: [2], 3: []}).is_antichain_of_poset([1,2,4])

to be an error message, not False.

However, if you do that, then this ticket should be postponed until that is ready.

[dcoudert]

comment:15

I prefer to have this ticket fixed now since it impacts other methods. For instance, g.vertex_connectivity() has special treatment for cliques. If g.is_clique() returns a wrong answer, then the answer of g.vertex_connectivity() is also wrong.

We can deal with the subgraph problem independently.

[jm58660]

comment:16

Replying to @dcoudert:

I prefer to have this ticket fixed now since it impacts other methods. For instance, g.vertex_connectivity() has special treatment for cliques. If g.is_clique() returns a wrong answer, then the answer of g.vertex_connectivity() is also wrong.

We can deal with the subgraph problem independently.

OK. I'll try to review this in a day or two.

[jm58660]

Reviewer: Jori Mäntysalo

[jm58660]

comment:17

Seems to be OK. ("Trivially complicated code", but there is no other way as there are so many combinations of parameters.)

[dcoudert]

comment:18

Thank you.

[jm58660]

comment:19

rc for 8.3 is already out.

[vbraun]

Changed branch from u/dcoudert/25696_is_clique to 50df10e