2
$\begingroup$

Given a graph $G$ with $n$ vertices, I need to find a subgraph consisting of $m$ vertices $\{v_1,\ldots,v_m\}$, and the induced subgraph of this subgraph should also be a tree.

For example, suppose $G$ is a $3\times3$ grid graph, and the subgraph should include vertices $\{6,8,1\}$. Shown below is an example of a subgraph (edges in green) which includes these vertices.

enter image description here

However, its induced subgraph is

enter image description here

which is not a tree.

A solution for this specific example would be;

enter image description here

and its induced subgraph,

enter image description here

which is a tree.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ why is it that the subgraph formed by green edges in the second picture not a tree? $\endgroup$
    – kglr
    May 28 at 19:44
  • $\begingroup$ the subgraph is a tree, however the induced subgraph, which includes all the edges between the vertices in the original graph, is not. $\endgroup$
    – Dotman
    May 28 at 19:49
  • 1
    $\begingroup$ According to the definition in the link, the only induced subgraph formed by vertices $\{6,8,1\}$ in your example is the graph with vertex list $\{6,8,1\}$ and no edges. $\endgroup$
    – kglr
    May 28 at 19:49
  • 1
    $\begingroup$ Ah ok, i understand the confusion..i should've been more clear. The induced subgraph is formed from all the vertices in the subgraph, not just $\{6,8,1\}$. $\endgroup$
    – Dotman
    May 28 at 19:56
  • $\begingroup$ thank you Dotman. $\endgroup$
    – kglr
    May 28 at 19:59

1 Answer 1

Reset to default
5
$\begingroup$

Update:

A less-brute force modification:

ClearAll[findInducedSubtree]
findInducedSubtree[g_, vlst_] /; {} === FindCycle[Subgraph[g, vlst], ∞, 1] := 
 Module[{k = 1, res = {}}, 
   While[{} === (res = Flatten @ 
    Map[If[TreeGraphQ @ #, #, {}] & @ Subgraph[g, Join[vlst, #]] &]@
    Subsets[Complement[VertexList@g, vlst], {k++}])]; 
   MinimalBy[VertexCount] @ res]

Examples:

vlst = {6, 8, 1};

gg = GridGraph[{3, 3}, 
   PlotTheme -> "ThickEdge", VertexLabels -> Automatic,
   VertexSize -> (Alternatives @@ vlst -> Medium)];

Row[HighlightGraph[gg, #, ImageSize -> 300] & /@ 
  findInducedSubtree[gg, vlst]]

enter image description here

vls = {21, 2, 3, 7, 35, 11, 32, 26, 30, 16, 8, 25};

gg6 = GridGraph[{6, 6}, PlotTheme -> "ThickEdge", 
   VertexLabels -> Automatic, 
   VertexSize -> (Alternatives @@ vls -> Medium)];

HighlightGraph[gg6, Subgraph[gg6, vls], ImageSize -> 400]

enter image description here

pics = HighlightGraph[gg6, #, ImageSize -> 400] & /@ 
  findInducedSubtree[gg6, vls];


Multicolumn[pics, 4]

enter image description here

SeedRandom[1];

rg = RandomGraph[{30, 50}, PlotTheme -> "ThickEdge", 
   VertexLabels -> Automatic, GraphHighlightStyle -> "Thick", 
   EdgeStyle -> AbsoluteThickness[5], 
   VertexSize -> (Alternatives @@ vls -> Large)];

A vertex list that does not induce a subgraph with cycles:

While[{} =!= FindCycle[
    Subgraph[rg, vls = RandomSample[Range@30, 12]], ∞, 1]];
vls

{3, 10, 14, 27, 17, 28, 18, 8, 9, 23, 4, 20}

HighlightGraph[rg, Subgraph[rg, vls], ImageSize -> 500]

enter image description here

trees = findInducedSubtree[rg, vls];

Row[HighlightGraph[rg, #, ImageSize -> 600] & /@ trees]

enter image description here

Original answer:

A brute-force approach:

ClearAll[selectSubgraphs]

selectSubgraphs[g_, vlst_] := Select[TreeGraphQ] @ 
   Map[Subgraph[g, #] &] @
   Select[ContainsAll @ vlst] @ 
   Subsets[VertexList @ g, {Length @ vlst, VertexCount @ g}]

Examples:

vlst = {6, 8, 1};

gg = GridGraph[{3, 3}, 
   PlotTheme -> "ThickEdge", VertexLabels -> Automatic,
   VertexSize -> (Alternatives @@ vlst -> Medium)];

Multicolumn[HighlightGraph[gg,  #] & /@ selectSubgraphs[gg, vlst], 4]

enter image description here

If desired, select the subgraphs with minimum number of vertices:

Row[HighlightGraph[gg, #, ImageSize -> 300] & /@ 
  MinimalBy[VertexCount]@selectSubgraphs[gg, vlst]]

enter image description here

Improve this answer
$\endgroup$
6
  • $\begingroup$ This is nice, thank you. However its not really applicable in cases beyond $5\times5$. Im looking to analyse this problem upto $10\times10$ case. Hence I'm not marking this as the answer (yet). $\endgroup$
    – Dotman
    May 29 at 12:31
  • $\begingroup$ is your base graph always a grid graph ? $\endgroup$
    – kglr
    May 29 at 13:31
  • $\begingroup$ Not necessarily…. However It would be nice to have a solution that at least works on grid graphs $\endgroup$
    – Dotman
    May 29 at 14:15
  • $\begingroup$ Dotman, please see the update. $\endgroup$
    – kglr
    May 29 at 14:59
  • 1
    $\begingroup$ your second example is wrong. 6,16 and 17,27 are neighbours, hence the induced subgraph is not a tree $\endgroup$
    – Dotman
    May 29 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.