2
$\begingroup$

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.

Assume these degree sequences are graphical: there exist simple graphs (no loop, no multiple edge) with degree sequence $a_i$, $b_i$, and $c_i$.

How to decide if there exists a simple graph $G_c=(V,E_c)$ with degree sequence $c_i$ being the disjoint union of two graphs $G_a = (V,E_a)$ and $G_b = (V,E_b)$ with degree sequence $a_i$ and $b_i$, respectively?

If such a triplet of graphs exists, how to find an instance? How to uniformly sample a random one?

(Disjoint union means here that $E_a \cup E_b = E_c$ and $E_a \cap E_b = \emptyset$; $E_a$ and $E_b$ form a partition of $E_c$.)

(This is a follow-up of the discussion where we established that there is not always such graphs.)

(A bit of motivation. We encounter this problem in the context of a benchmark generation for anomalous subgraph detection: the graph $G_a$ represents normal links, the graph $G_b$ represents anomalous ones that we want to detect, and the graph $G_c$ is our problem input. We use various parameters to build $G_a$ and $G_b$, thus $G_c$, and check if we are able to find $G_b$ in $G_c$.)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think you care about the running time complexity? If not, you can just try all possible combinations. Your problem might be NP-complete. If your graph $G_c$ is provided, you can find $G_a$ and $G_b$ by solving perfect b-matching on $G_c$. $\endgroup$
    – maxdan94
    Commented Jan 19, 2021 at 23:44
  • $\begingroup$ You are right, complexity clearly is a concern here. A heuristic would be fine, but not an approximate solution. Using b-matching seems promising indeed! $\endgroup$
    – Matthieu Latapy
    Commented Jan 20, 2021 at 7:54
  • $\begingroup$ My case is much simpler, though: I am asking for the existence and sampling of such graph triplets; $G_c$ is not a priori given. I may for instance start with simple graphs $G_a$ and $G_b$ leading to a multi-graph $G_c$ and then remove multi-edges using swaps. This is not always possible, but depends on some properties of considered degree sequences. $\endgroup$
    – Matthieu Latapy
    Commented Jan 20, 2021 at 8:33
  • $\begingroup$ A somewhat related question was posted here: mathoverflow.net/questions/383913/… $\endgroup$
    – Matthieu Latapy
    Commented Feb 22, 2021 at 1:10

0

Reset to default

You must log in to answer this question.