VERY CHALLENGING QUESTION OF NETWORK FLOW

[Yaron Wittenstein]

Hi all here is a a good link:

http://www.cs.uiuc.edu/class/sp06/cs473g/exbook.pdf



I have no idea how to solve question 3.1.11 (page 33 in the pdf file)
the one with the matrice of 0-1...

If somebody knows what network flow should be constructed
please help me

P.S: 3.1.12 (Unique cut) I have no idea too...

Thank you!!!!

[Mg9H]

Hi all here is a a good link:

http://www.cs.uiuc.edu/class/sp06/cs473g/exbook.pdf



I have no idea how to solve question 3.1.11 (page 33 in the pdf file)
the one with the matrice of 0-1...

If somebody knows what network flow should be constructed
please help me

P.S: 3.1.12 (Unique cut) I have no idea too...

Thank you!!!!

What does "rearrangeable matrix" mean?

[Sedefcho]

Yes, unfortunately the PDF file does not define what
"rearrangeable matrix" means. If you can give me the
definition maybe I will be able to help you.

Regards,
Peter

[Yaron Wittenstein]

I'll write the question as it is in the 'Algorithm Design' book:
(Chapter 7: Network flow page 428 question 22)

Let M be an nxn matrix with each entry equal to either 0 or 1.
Let mij denote an entry in row i and column j. A digonal entry
is one of the form mij for some i.

Swapping rows i and j of the Matrix M denotes the following action:
we swap the values mik and mjk for k = 1, 2, ..., n.
Swapping two columns is defined analogously.

We say the M is REARRANGEABLE if it is possible to swap some of the
pairs of rows and some of the pairs of columns (in any sequence) so that,
after all the swapping, all the digonal entries of M are equal to 1.

The problem: Give a polynomial-time algorithm (i.e using network-flow)
that determines whether a matrix M with 0-1 entries is REARRANGEABLE

[Mg9H]

If that is the definition of REARRABLEABLE, I believe a matrix NxN is rearrangeable iff it has a perfect matching (which can be determined in O(N^3)).

I'll write the question as it is in the 'Algorithm Design' book:
(Chapter 7: Network flow page 428 question 22)

Let M be an nxn matrix with each entry equal to either 0 or 1.
Let mij denote an entry in row i and column j. A digonal entry
is one of the form mij for some i.

Swapping rows i and j of the Matrix M denotes the following action:
we swap the values mik and mjk for k = 1, 2, ..., n.
Swapping two columns is defined analogously.

We say the M is REARRANGEABLE if it is possible to swap some of the
pairs of rows and some of the pairs of columns (in any sequence) so that,
after all the swapping, all the digonal entries of M are equal to 1.

The problem: Give a polynomial-time algorithm (i.e using network-flow)
that determines whether a matrix M with 0-1 entries is REARRANGEABLE

[Yaron Wittenstein]

can you please define the network flow?
what will be the perfect matching?

[Mg9H]

can you please define the network flow?
what will be the perfect matching?

Think of your matrix as a adjacency matrix for a bipartite graph with N vertices in each set, i.e. M [j] = the capacity of an edge from X to Y [j] (i, j = 1, 2, .., N).

Now, add 2 more vertices S & T to this graph, add N edges from S to X (i = 1, .., N) and N other edges from Y [j] (j = 1, .., N) to T (all these 2N edges have capicity 1) .

Then, the original NxN matrix is rearrangeable iff the maxflow in this new graph (network) equals to N.