#StackBounty: #algorithms #graphs #coin-change Algorithm for fewest number of moves with artificial minimum

Bounty: 50

I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum.

To summarize, I built an undirected graph with edges representing possible moves of 1’s, 10’s, 100’s, etc to get from one value to another.

public static UndirectedGraph<int, IEdge<int>> GetMinimumMovesGraph()
{
    var graph = new UndirectedGraph<int, IEdge<int>>();
    // load a graph that handles bases of 10's up to 10,000
    for (int i = 0;i <= 10000; i++)
    {
        for (int j = i+1; j <= 10000; j++)
        {
            // only add edges if difference is base of 10
            if (j - i == 1 || j - i == 10 || j - i == 100 || j - i == 1000)
            {
                graph.AddVerticesAndEdge(new UndirectedEdge<int>(i, j));
            }
        }
    }
    return graph;
}

So, the minimum distance from 46 to 121 is 8 steps/moves:

  • add 100 (146) – 1 move
  • subtract 10 (136) – 1 move
  • subtract 10 (126) – 1 move
  • subtract 1 five times (121) – 5 moves

Let’s say the minimum number of steps through the graph has to be greater than 8 e.g. 10, 15, etc.

What if I had to specify an odd or even number of moves?

Can this be done with the existing graph, or is there another graph structure that would support it? Weights, directions? Could I build the graph differently to describe the criteria e.g. not adding edges until certain number of edges exist back to the source, but then I would need Dijkstra on every iteration at build time


Get this bounty!!!

#StackBounty: #algorithms #graphs #approximation #vertex-cover Vertex cover of bipartite graph

Bounty: 50

A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
A minimum vertex cover is a vertex cover with minimal cardinality.

https://codeforces.com/blog/entry/63164

Consider a set of all minimum vertex covers of a given bipartite graph,
our task is to divide all vertices of the graph into three sets.

A vertex is in set

  • N (“Never”) if there is no minimum vertex cover containing this vertex.
  • A (“Always”) if it is a part of every minimum vertex cover of the given graph.
  • E (“Exists”), otherwise.

I don’t understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

This is the graph I have ($2K_2$) two edges in the maximum matching:

2K_2

For the first edge I took left vertex in the cover
$x_1=0$ (according to the blog in the link)
for the second edge I took right vertex in the cover $x_2=1$.

Questions:

  1. How final 2-sat will be true?
  2. Can anyone explain what will be the relation between x1 and x2 ?


Get this bounty!!!

#StackBounty: #algorithms #graphs #graph-theory #optimization #heuristics Morphing Hypercubes, Token Sliding and Odd Permutations

Bounty: 200

A month ago, I asked the following question math.exchange (https://math.stackexchange.com/questions/3127874/morphing-hypercubes-and-odd-permutations), but for completeness, I will include the details here.


Let $Q_n$ denote the $n$-dimensional hypercube graph — the graph with vertex set $V_n = big{v : v in {0, 1}^n big}$ and edges $$E_n = big{(u,v) : u, v in V_n text{ with } u text{ and } v text{ having Hamming distance one}big}$$

Let $H$ denote a subgraph of $Q_n$ that is isomorphic to $Q_{n’}$, for some input parameter $n’ leq n$ (i.e. $H$ is an $n’$-dimensional subcube of $Q_n$). Every vertex $v$ in $H$ has a token (or a pebble) with a label $ell(v)$. Next, we partition $H$ into $2^{n’ – d}$ vertex disjoint subgraphs $H_1, ldots, H_{2^{n’-d}}$ each isomorphic to $Q_d$ where $d leq n’$ is a second parameter.

We can think of each $H_i$ as a ternary string $s_i in {0, 1, }^n$ such that $s_i$ has exactly $d$ $$‘s. These represent free coordinates. For each $s_i$, we define a mapping $f_i : {0, 1, }^n to {0, 1, *}^n$ such that the $j$-th coordinate of $f_i(s_i)$ is a $$ if and only if the $j$-th coordinate of $s_i$ is a $*$. So intuitively, each $f_i$ maps a $d$-dimensional subcube to another $d$-dimensional subcube on the same axes. Let $H’$ denote the subgraph obtained by decomposing $H$ as described above and applying the $f_i$‘s on its $2^{n’-d}$ pieces — in other words, $H’$ is the subgraph induced by the vertices from each $f_i(s_i)$. If $H’$ is also isomorphic to $Q_{n’}$, then I call $H’$ a $texttt{morph}$ of $H$. When a morph operation is applied on $H$, the tokens are also moved appropriately.

So my problem is the following. Given $H$, I would like to apply/find a sequence of morph operations to obtain a graph $H”$ that “finishes where $H$ started” — By this, I mean that the ternary string that represents $H$ must be the same as $H”$. The caveat is the following: if we consider the permutation induced by the tokens (since the tokens finish on the same subset of vertices that they started on), I want them to induce an odd permutation.

To help clarify, consider the following example with $n=3$, $n’=2$ and $d=1$. Let $H$ denote the 2D face of $Q_3$ induced by $0**$. We place four tokens on those vertices with labels $A,B,C,D$$A$ is placed on $000$, $B$ on $001$, $C$ on $010$ and $D$ on $011$. Now, consider the following three morph operations:

1) Partition ${A,B,C,D}$ into pairs ${A,B}$ and ${C, D}$. These can be represented by ternary strings $00$ and $01$ respectively. We map $00* to 11$ and leave $01$ unchanged (i.e. just apply the identity). This gives us a new graph isomorphic to $Q_2$ with token placement $A$ on $110$, $B$ on $111$, $C$ on $010$ and $D$ on $011$. Note that this new square doesn’t have the same “orientation” as the first, since it has a ternary string representation of $1$.

2) Next, partition the newly obtained $1$ into $10$ and $11$ — pairing the tokens ${A, C}$ and ${B, D}$. We map $*10 to *01$ to obtain the square $**1$ ($*11$ is left unchanged). The tokens are located as follows: $A$ on $101$, $B$ on $111$, $C$ on $001$, and $D$ on $011$.

3) Finally, we partition the obtained $1$ into $11$ and $01$ — pairing the tokens ${A,B}$ and ${C,D}$. We map $11 to 00$, which gives us our graph $H”$ induced by the square $0$ (just as it was with $H$). If we look at the placement of the tokens, we see that $A$ still on $000$, $B$ is now on $010$, $C$ is now on $001$ and $D$ is still on $111$. The permutation induced by the new positioning of the tokens is an odd permutation as required.

So now I am interested in the case when $d=2$. I would like to find a pair of values for $n$ and $n’$ where such a sequence of morph operations exist. I don’t necessarily want the tightest values of $n$ and $n’$, nor am I picky about the number of morph operations.


I haven’t been able to prove that this is possible, so I have been writing code to perform an “exhaustive search”. I can show that this is not possible for values of $n$ less than or equal to $4$, but the search space grows much to quickly.

So my question is two-fold: 1) What kinds of optimizations should I consider? I am interested in practical heuristics that might help, not necessarily theoretical guarantees, and 2), is there a cleaner way to frame this problem? Just defining what a morph operation is takes a lot of work, let alone the rest.

I apologize for the wall of text, and can try to add missing details or clarifications if necessary.


Get this bounty!!!

#StackBounty: #algorithms #graphs #shortest-path Finding a negative cycle in a bipartite graph

Bounty: 50

The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where the edges in one direction (from X to Y) are all positive and the edges in the other direction (from Y to X) are all negative?


One idea that I considered is to solve two instances of the minimum-weight assignment problem: one with only the edges from X to Y, and one with only the edges from Y to X. Combining the two assignments gives a directed cycle in the original graph. However there are two problems with this idea:

  • The computational problem of finding a minimum-weight assignment is not necessarily smaller than Bellman-Ford, for example the Hungarian algorithm requires time $O(|V|^3)$.
  • The directed cycle found in this way is not necessarily minimum-weight in the original graph; it is possible that the original graph has a negative cycle while this algorithm will yield only a positive cycle. For example, consider a graph with four vertices in each side, with the following weights:
    begin{align*}
    w(x_1to y_1) = w(x_2to y_2) &= 1
    \
    w(y_2to x_1) = w(y_1to x_2) &= -2
    \
    w(x_3to y_3) = w(x_4to y_4) &= 5
    \
    w(y_4to x_3) = w(y_3to x_4) &= -3
    end{align*}

    and all other weights are $+infty$.

There is a negative cycle $x_1to y_1to x_2to y_2$ (total weight -2). However, the minimum-weight assignment from X to Y has weight 12 and the minimum-weight assignment from Y to X has weight -10 so the total is positive.


Get this bounty!!!

#StackBounty: #graphs #graph-isomorphism What is the current fastest algorithm for finding the maximum common subgraph?

Bounty: 50

First of all, it’s my first time in #ComputerScience at StackExchange so, my apologies if I’m making some newbie mistake when asking this question.

So, I’m currently researching algorithms for finding the maximum common subgraph isomorphism and after reading a lot of papers I’m still confused about what is the state-of-the-art algorithm for finding the maximum common subgraph between 2 graphs. Also, all the algorithms I’ve read about work with 2 graphs (directed or undirected) but none directly work with more than 2 graphs.

In summary, my questions are:

  1. Which is considered the fastest/state-of-the-art algorithm for finding the MCSI? Is it the VF2 algorithm?
  2. Also, does this algorithm work with more than 2 graphs at the same time?
  3. Any alternate algorithm that works with N graphs?

Thanks in advance!


Get this bounty!!!