Hi, I am writing my bachelor thesis and I came across a study which mentions finding a 2-3 subgraph and a 2-4 subgraph of an undirected graph as one of its subtask but it doesn't mention an algorithm to do it but it just says that it is done using DFS.
I couldn't really find anything useful online solving these problems.
A 2-3 subgraph is a subgraph where each node has degree 2 or 3 in this subgraph (we remove edges which go to nodes outside the subgraph) and our task is to find a maximal 2-3 subgraph (it doesn't have to be maxmimum in terms of size just that we can't add another node to it). A 2-4 subgraph is just the same but with 2, 3 and 4.
Can anyone help by describing an algorithm or linking an article/paper?
Auto comment: topic has been updated by YahiaSherif (previous revision, new revision, compare).
For 2-3 you could go like this. Start from any induced cycle, which is a 2-subgraph (there are at least a couple of ways to find one), so in particular it is a 2-3 subgraph as well. Then you can try adding vertices outside of it to it until you can't add anything else. I believe everything could be done in linear time, but I did not think of all the details.
For a 3-4 subgraph you can deal with the maximality part in the same way, but you would need to find any 3-4 subgraph to start with. For that I don't have a good quick idea yet. In particular, you will find 2-3 subgraph in any graph that is not a forest, but characterisation of graphs that have 3-4 subgraphs is probably not obvious?
Yes, I had the same general idea of starting with a cycle and so. but the challenge was when adding nodes I can't nodes one by one as it may end up in situation where a node with degree 1 is in the subgraph which is not allowed. The alternative was to try and connect 2 nodes which already have degree 2 with a path which is not in the subgraph completely but I get the feeling that this solution is not complete.
Sorry I made a mistake about the second one, it is 2-4 subgraph which means 2,3,4 are allowed.
Also it will not be linear as in the way I suggested because I would have to dfs from each node with degree 2 I think
In order to find an induced cycle? Not really. Let's compute DFS tree from any vertex and take the shortest edge which does not belong to DFS tree. Shortest meaning between vertices with the smallest difference of their depths. It will create an induced cycle along with the path between them in the tree. You can find one in a bit different way by inspecting BFS tree as well
I meant adding nodes to the subgraph. It isn't linear in the way I suggested.
I am not really sure what is the issue with the part ensuring the maximality. If a node has degree one, it couldn't be added to our subgraph in the first place. It could be the case that a node outside couldn't be added, but after some time can be added (because its degree to already included vertices rose from 0 or 1 to 2 or 3), but that is not any problem if you do it in the following way:
while(can add some vertex) { add one }which can be expressed in a more elaborated way
When expressed this way, it will be too slow, but you should be able to optimize it by tracking for each vertex its current degree to already included vertices and whether it has an included neighbor with degree 3 (which will prevent adding the vertex itself).
And if we are talking about 2-4 subgraph and not 3-4 subgraphs then it is easy. The only difference will be tracking whether you have an included neighbor with degree 4 instead of 3
Check this example:
Graph has 6 nodes.
Edges: 1-2, 1-3, 2-3, 2-4, 4-5, 3-5, 2-6
Assume the first cycle we find is 1-2-3. Then when we try to add new nodes we add node 6 to the subgraph. Now node 2 already has 3 edges in the subgraph, so we can't add node 4 but we add node 5. So now our subgraph is 1, 2, 3, 5, 6 which has nodes 5,6, having degree 1 in the subgraph.
Why do you add 6 if it has degree 1 :|? 1,2,3,6 is not a 2-3 subgraph. 1,2,3 is already a maximal 2-3 subgraph, you can't add anybody to it.
I can add 4 and 5 to 1-2-3 and it would still be a 2-3 subgraph. Also if for example we had a node 7 which was connected to 6 then 6 would have degree 2 in the original graph.
Ouch, sorry. Forget everything I said about maximality :(.
As an excuse I could say that in majority of cases when maximality is considered, families of good sets are hereditary (i.e. if A is good then each subset of A is good as well) and then you can ensure maximality by adding elements one by one, while here our property is not hereditary and we cannot add neither 4 not 5 on their own, but adding them both works. Moreover, your wording was misleading as well as you have defined maximality as "we cannot add another node to it" :P. I know what maximality means, but that already set me on the wrong track I was familiar with xD
xD No worries.
Auto comment: topic has been updated by YahiaSherif (previous revision, new revision, compare).
Let's call the graph $$$G$$$. Start with any 2-3 subgraph $$$H$$$ in $$$G$$$, and then do the following repeatedly while you can:
This should find a maximal 2-3 subgraph in linear time in the number of edges. The case for 2-4 is very similar to this too.
Very interesting, thank you! Do you know if this was published before, if so where so I that I can reference it in my thesis?
No, I have no idea if it was.