Is it bipartite?

Question

A bipartite graph is a graph whose vertices can be divided into two disjoint set, such that no edge connects two vertices in the same set. A graph is bipartite if and only if it is 2-colorable.

---

Challenge

Your task is to, given the adjacency matrix of an undirected simple graph, determine whether it is a bipartite graph. That is, if an edge connects vertices i and j, both (i, j) and (j, i) entry of the matrix are 1.

Since the graph is undirected and simple, its adjacency matrix is symmetric and contains only 0 and 1.

Specifics

You should take an N-by-N matrix as input (in any form, e.g. list of lists, list of strings, C-like int** and size, flattened array, raw input, etc.).

The function/program should return/output a truthy value if the graph is bipartite, and falsy otherwise.

Test Cases

['00101',
 '00010',
 '10001',
 '01000',
 '10100'] : False
['010100',
 '100011',
 '000100',
 '101000',
 '010000',
 '010000'] : True (divide into {0, 2, 4, 5} and {1, 3})
['00',
 '00'] : True

Scoring

Builtins that compute the answer directly are banned.

This is code-golf, so the shortest program (in bytes) by the end of this month wins!

Answer 1

Husk, 17 bytes

§V¤=ṁΣṠMSȯDfm¬ṀfΠ

Prints a positive integer if the graph is bipartite, 0 if not. Try it online!

Explanation

This is a brute force approach: iterate through all subsets S of vertices, and see whether all edges in the graph are between S and its complement.

§V¤=ṁΣṠMSȯDfm¬ṀfΠ  Implicit input: binary matrix M.
                Π  Cartesian product; result is X.
                   Elements of X are binary lists representing subsets of vertices.
                   If M contains an all-0 row, the corresponding vertex is never chosen,
                   but it is irrelevant anyway, since it has no neighbors.
                   All-1 rows do not occur, as the graph is simple.
      ṠM           For each list S in X:
              Ṁf   Filter each row of M by S, keeping the bits at the truthy indices of S,
        S  fm¬     then filter the result by the element-wise negation of S,
         ȯD        and concatenate the resulting matrix to itself.
                   Now we have, for each subset S, a matrix containing the edges
                   from S to its complement, twice.
§V                 1-based index of the first matrix
  ¤=               that equals M
    ṁΣ             by the sum of all rows, i.e. total number of 1s.
                   Implicitly print.

Answer 2

Wolfram Language (Mathematica), 26 25 bytes

Tr[#//.x_:>#.#.Clip@x]<1&

Try it online!

How it works

Given an adjacency matrix A, we find the fixed point of starting with B=A and then replacing B by A²B, occasionally clipping values larger than 1 to 1. The k^th step of this process is equivalent up to the Clip to finding powers A^2k+1, in which the (i,j) entry counts the number of paths of length 2k+1 from vertex i to j; therefore the fixed point ends up having a nonzero (i,j) entry iff we can go from i to j in an odd number of steps.

In particular, the diagonal of the fixed point has nonzero entries only when a vertex can reach itself in an odd number of steps: if there's an odd cycle. So the trace of the fixed point is 0 if and only if the graph is bipartite.

Another 25-byte solution of this form is Tr[#O@n//.x_:>#.#.x]===0&, in case this gives anyone ideas about how to push the byte count even lower.

Previous efforts

I've tried a number of approaches to this answer before settling on this one.

26 bytes: matrix exponentials

N@Tr[#.MatrixExp[#.#]]==0&

Also relies on odd powers of the adjacency matrix. Since x*exp(x²) is x + x³ + x⁵/2! + x⁷/4! + ..., when x is a matrix A this has a positive term for every odd power of A, so it will also have zero trace iff A has an odd cycle. This solution is very slow for large matrices.

29 bytes: large odd power

Tr[#.##&@@#~Table~Tr[2#!]]<1&

For an n by n matrix A, finds A²ⁿ⁺¹ and then does the diagonal check. Here, #~Table~Tr[2#!] generates 2n copies of the n by n input matrix, and #.##& @@ {a,b,c,d} unpacks to a.a.b.c.d, multiplying together 2n+1 copies of the matrix as a result.

53 bytes: Laplacian matrix

(e=Eigenvalues)[(d=DiagonalMatrix[Tr/@#])+#]==e[d-#]&

Uses an obscure result in spectral graph theory (Proposition 1.3.10 in this pdf).

Answer 3

JavaScript, 78 bytes

m=>!m.some((l,i)=>m.some((_,s)=>(l=m.map(t=>t.some((c,o)=>c&&l[o])))[i]&&s%2))

Input array of array of 0 / 1, output true / false.

f = 

m=>!m.some((l,i)=>m.some((_,s)=>(l=m.map(t=>t.some((c,o)=>c&&l[o])))[i]&&s%2))

run = () => o.value=f(i.value.trim().split('\n').map(v=>v.trim().split('').map(t=>+t)))

<textarea id=i oninput="o.value=''" style="width:100%;display:block;">010100
100011
000100
101000
010000
010000
</textarea>
<button type=button onclick="run()">Run</button>
<div>Result = <output id=o></output></div>

Answer 4

Pyth, 25 bytes

xmyss.D.DRx0dQx1d.nM*FQss

Try it online!

This returns -1 for falsy, and any non-negative integer for truthy.

How it works

xmyss.D.DRx0dQx1d.nM*FQss ~ Full program, receives an adjacency matrix from STDIN.

                    *FQ   ~ Reduce (fold) by cartesian product.
                 .nM      ~ Flatten each.
 m                        ~ Map with a variable d.
         R   Q            ~ For each element in the input,
       .D                 ~ Delete the elements at indexes...
          x0d             ~ All indexes of 0 in d.
     .D                   ~ And from this list, delete the elements at indexes...
              x1d         ~ All indexes of 1 in d.
    s                     ~ Flatten.
   s                      ~ Sum. I could have used s if [] wouldn't appear.
  y                       ~ Double.
x                         ~ In the above mapping, get the first index of...
                       ss ~ The total number of 1's in the input matrix.

This works in commit d315e19, the current Pyth version TiO has.