#StackBounty: #complexity-theory #graphs #np-complete #combinatorics #circuits Example of *small* non monotone circuit such that any eq…

Bounty: 400

A “general” Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:

  1. fan-in=2 for the AND and OR nodes
  2. fan-n=1 for the NOT nodes
  3. fan-in=0 for the IN nodes
  4. fan-out=0 to exactly one node (the OUT node)
  5. Unbounded fan-out to the rest of the nodes (but the OUT node)

A monotone circuit is a Boolean circuit with 0 vertices labeled as “NOT”.

The size of a circuit is the number of “gates” (vertices with labels “AND”, “OR” or “NOT”) it contains.

In Yuval’s answer here I’ve learned of two examples (Tardos function and bipartite perfect matching) where it has been proven that monotone circuits admit greater size than general Boolean circuits, but I cannot get the intuition, as I don’t have any concrete small size example in hand.

Hence, my question is: could you please supply me with an example of a small (say, up to 10-20 gates) non monotone circuit such that any equivalent monotone circuit has greater size?

Edit

I guess that the smallest-size circuit computes the 3-Clique decision problem, as this is the smallest size where we can exploit fast matrix multiplication for the k-Clique problem (where non-monotone circuits may have smaller size than their equivalent monotone circuits, as I mentioned before).

Since the key part of exploiting fast matrix multiplication is (roughly): does $X^2$ contain any non-zero?
Hence, I guess that a circuit that computes this decision problem is the minimal-size one. So, it is equivalent to $$bigvee_{i,j,kleq n}{(x_{ij}wedge x_{jk})}equivbigvee_{i,jleq n}left(x_{ij}wedge{left(bigvee_{kleq n} x_{jk}right)} right)$$.

If it is true, we just need to find some small $n$ (preferably, the smallest $n$), and some non-monotone function of size $lneq n^2cdot (n+1)=n^3+n^2$, which is the size of RHS, which is probably the minimal-size monotone circuit that computes this function.

Now, smallest size for Strassen is $n=4$, so it admits $n^2=4^2=16$ variables, but I guess that simpler manipulation than Strassen could do the desired on smaller $n$, and with simpler manner.

To sum up, I almost get it, but still do not have an explicit simple and small example in hand.


Get this bounty!!!

#StackBounty: #graphs #trees #minimum-spanning-tree #spanning-trees MST with possibly minimal diameter

Bounty: 50

I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph is undirected (just like in Christofides algorithm). The point is, the problem I am working on requires me to find the MST with possibly lowest diameter (the number of nodes on the longest path between any two leaf nodes, equivalently, for the purpose of measuring the diameter one can treat all the edges of the MST as if they had the weight equal to 1).

I know that Boruvka’s, Prim’s and Kruskal’s algorithm can be used to find some MST, but can I influence them somehow to prefer the shortest (in the terms of the diameter) trees possible?

If the answer to the question above is negative, are there any algorithms or methods which either yield MST with some bounds on the tree diameter or, at least, are there any known methods of obtaining a bound on MST diameter for a given graph?


Get this bounty!!!

#StackBounty: #algorithms #graphs #artificial-intelligence Use AI to analyze undirected weight graph and generate two sub graphs

Bounty: 50

I have a weighted undirected graph G0, from which I want to derive weigthed undirected graphs G1 and G2.

  • All nodes in G0 have a degree of at least one.
  • G1 and G2 can contain the same node but not the same edge.
  • All nodes in both G1 and G2 should have a degree of at least one.
  • All edges from G0 should be contained in either G1 or G2
  • Both G1 and G2 are subgraphs of G0 and cannot contain additional nodes.

Let’s assume that the sum of all the edges in G0 = x.

I need to find the pair of G1 and G2 for which the sum of all edges in G1 is closest to x/2

How would you go about solving that?

Edit: After much hassle due to my lack of explanatory powers, here is a better explanation of the problem (this is for an unweighted graph, but it will at least point me in the general direction of a suitable algorithm, also it avoids technical terms because is obvious that I struggle understanding them at the moment)

Lets assume that we have an undirected Graph with Vertices A,B,C,D,E

A --- B 
|   / | 
|  /  |  C
| /   | / 
D --- E 

Which means an adjacency matrix like this one:

  A  B  C  D  E
A -  1  0  1  0
B 1  -  1  1  1
C 0  1  -  0  1
D 1  1  0  -  1
E 0  1  1  1  -

Assuming all edges are undirected, we have the following edges:

(a,b) (a,d) (b,d) (b,e) (b,c) (e,d) (e,c)

What I want is that through AI, I can take that graph and generate two groups of edges of roughly the same size. (In this particular case, since we have 7 edges, we would get a group of 3 edges and another one of 4 edges.

Group 1: (a,b) (a,d) (b,d) (e,d)
A --- B 
|   / 
|  /  
| /     
D --- E 

Group 2: (b,e) (b,c) (e,c)
B 
| 
|  C
| / 
E 

Notice that all edges in each group are connected by at least one node, that is a requirement.

Another valid solution could be, for example:

Group 1: (d,a) (a,b) (b,c) (c,e)
A --- B 
|       
|       C
|       / 
D     E 
Group 2: (d,b) (b,e) (e,d)
      B 
    / |
   /  |
  /   | 
D --- E 

And so on, as you see there are many valid solutions but I want to know if there’s an algorithm to find one.


Get this bounty!!!

#StackBounty: #graphs #np-complete #np-hard #decision-problem #set-cover maximum coverage version of dominating set

Bounty: 50

The dominating set problem is :

Given an $n$ vertex graph $G=(V,E)$, find a set $S(subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := {x~ | text{ either $x$ or a neighbor of $x$ lies in $S$}}$$

My question is if the following (new problem) has a definite name in literature, and if not what should be the most appropriate name.

New Problem: Given an $n$ vertex graph $G=(V,E)$ and an integer $k$ , find a set $S(subseteq V)$ of size $k$ such that $|N[S]|$ is maximized.

For the second problem, some of the names I have seen in the literature are maximum-graph-coverage; partial-coverage; k-dominating-set, (however, the exact same names are also used in other contexts).


Get this bounty!!!

#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!!!