shortest directed odd cycle

Question

6.1.4 Describe an algorithm based on breadth-first search for finding a shortest odd cycle in a graph.

6.3.5 Describe an algorithm based on directed breadth-first search for finding a shortest directed odd cycle in a digraph.

what is most importent is that it must be a directed graph not necessary bfs but must be the shortest directed odd cycle!!!

Question was taken from "Graph Theory" by J.A. Bondy and U.S.R. Murty

thanks in advance!!!

Answer 1

Running BFS from every node and seeing what paths lead to the starting node should work. Pick the one that has an odd length and is minimum. O(n^2) running time. The same should work for the directed graph version.

I don't know if there's an O(n) solution, but I'd be interested in one myself.

Here's an attempt at solving this with a single DFS. I've only tested it on a few graphs. You have to give it the number of edges and you must have a node labeled 1. It prints the length of the shortest odd cycle in an undirected graph.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <iostream>

using namespace std;

const int maxn = 100;

void addNode(vector<int> G[], int x, int y)
{
    G[x].push_back(y);
    G[y].push_back(x);
}

void DFS(vector<int> G[], int node, int parent, int pos[], int stack[], int d, int &min)
{
    stack[d] = node;
    if (pos[node] != 0) // we have a cycle
    {
        int t = d - pos[node];
        if (t % 2 == 1 && t < min) // if it's odd and smaller than what we've found so far
        {
            // use what's in stack to get the actual cycle if you want.
            min = t;
        }
        return;
    }
    pos[node] = d;

    for (int i = 0; i < G[node].size(); ++i)
    {
        if (G[node][i] != parent)
        {
            DFS(G, G[node][i], node, pos, stack, d + 1, min);
        }
    }

    pos[node] = 0;
}

int main()
{
    vector<int> G[maxn];
    int pos[maxn]; // position of a node in the stack
    int stack[maxn];

    memset(pos, 0, maxn*sizeof(int));

    int min = (1 << 30);

    // read the edges of the graph.
    int m;
    cin >> m;
    int x, y;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y;
        addNode(G, x, y);
    }

    DFS(G, 1, 0, pos, stack, 1, min); // start DFS from node 1

    cout << min << endl;

    return 0;
}