Tag Archives: Hamiltonian Path

Consecutive Sets

This one moves slightly away from the matrix stuff we’ve been doing, but results in a pretty cool reduction.

The problem: Consecutive Sets.  This is problem SR18 in the appendix.

The description: Given a collection C of subsets of a finite alphabet Σ, and a positive integer K, can I find a string w from ∑* with K symbols or less, such that each element in C has its characters occur sequentially in w?

Example: Let ∑ = {a,b,c,d,e} and C = {{a,b,c}, {a,d,e}, {b,e}, {c,d}}

Then I can choose w to be dcbadeb, which is length 7, which is the best I could find. Notice how positions 2-4 contain {a,b,c}, positions 4-6 contain {a,d,e}, positions 6-7 contain {b,e}, and positions 1-2 contain {c,d}.

Reduction: This is “Problem 4” in the paper by Kou from last week.  He reduces from Hamiltonian Path.  So we start with a graph G=(V,E).  Our alphabet Σ (he uses “R” in the paper) has one symbol for each vertex in V and one symbol for each edge in E.  Our C set (he uses F in the paper) will have one set for each vertex.  The symbols in the set for a vertex i will consist of the edge symbols for the edges incident on i, and the vertex symbol for i itself.  K will be 2*|E|+1.

Notice that no two sets in C are subsets of each other (because they each hold a separate symbol from V), and that the intersection of 2 sets from C is a single edge (the edge connecting the two vertices corresponding to the sets), if that edge exists, and the intersection is empty otherwise.  A string w that we make will be based on a sequence of vertices (and their C sets).  Since each edge appears in two C sets, the “initial” size of w is 2|E| + |V|, if we have no overlap between C sets in w.  The question is how small can it get?

Since each C set can have at most one symbol of overlap with another C set, and that only happens if an edge exists between the vertices that define the C sets, the only way to create an overlap to reduce the size of w is to order the vertices such that there are edges between consecutive pairs of vertices.  G has a Hamiltonian Path if and only if we can order the vertices in such a way that there is an edge bewteen each part of consecutive vertices.  In w, that means we can overlap 1 symbol from each pair of consecutive C sets.  Since there are |V|-1 pairs of vertices in a path, the minimum size of w is 2|E| + |V| – (|V|-1) = 2|E| + 1 = K.

Difficulty: 5.  I think this is a neat reduction that students can get, though it might take a bit of work to make sure they understand the problem.

Consecutive Block Minimization

These next two problems are very similar to the “consecutive ones” problems we’ve been looking at lately.

The problem: Consecutive Block Minimization.  This is problem SR17 in the appendix.

The description: Given an m x n matrix A consisting of 0’s and 1’s and a positive integer K, can we permute the columns of A so that the permuted matrix (B) has K or less blocks of consecutive 1’s.  G&J define a “block” as an entry bij =1 where bi,j+1 = 0 or j = n.  So a “block” is one-dimensional, going across a row.

Example: Here’s a matrix:

1 0 1 0 1
1 1 1 0 1
0 0 1 1 0
0 1 1 0 0
1 1 0 0 1

Right now, this has 9 blocks (3 on the first row, 2 on the second and fifth, 1 on the third and fourth).

But we can permute the columns to get:

0 1 1 1 0
1 1 1 1 0
0 0 0 1 1
1 0 0 1 0
1 1 1 0 0

..for a total of 6 blocks.

Reduction: The paper by Kou has several reductions in it, we’ll be using this paper next week too.  This problem is “Problem 3” in the paper.  The problem uses Hamiltonian Path, but with costs for edges, so it’s really more like “Traveling Salesman on Paths”.   His “Problem 2” takes an instance of regular Hamiltonian Path and shows that this “Traveling Salesman on Paths” problem is NP-Complete on “cost graphs”.

Kou defines a “cost graph” of a matrix as a complete graph that has one vertex for each row and an edge cost of edge (i,j) as  the number of columns in A that have a 1 in row i and a 0 in row j.  He proves in the paper that a Hamiltonian Path on the cost graph has cost k iff there are k+c blocks of 1’s in the matrix, where c is the number of 1’s in the last row in the matrix.

So, the full reduction takes an instance of HP, creates an incidence matrix (as we defined in the Consecutive Ones Matrix Augmentation problem),  builds a cost graph of that, and uses that cost graph as the input to the Consecutive Block minimization problem.

Difficulty: 7. The cost graph construction is pretty hard to grasp, and you need to prove some extra lemmas along the way to show that the transformation works.

Consecutive Ones Matrix Partition

This is the problem I skipped over last week to get the two problems from Booth’s dissertation done together.

The problem: Consecutive Ones Matrix Partition.  This is problem SR15 in the appendix.

The description: Given an mxn matrix A consisting of 0’s and 1’s, can we partition the rows of A into two groups m1 and m2 such that the matrices A1 = m1x n and A2 = m2x n both have the consecutive ones property?

Example: Here’s the matrix that does not have the consecutive ones property.

0 1 1 1 1
1 1 1 0 1
0 0 1 1 0
0 1 1 0 0
1 1 0 0 0

But if we break it into two matrices, for example:

0 1 1 1 1
1 1 1 0 1
0 1 1 0 0

and

0 0 1 1 0
1 1 0 0 0

The two matrices have the consecutive ones property (the second matrix already has it, the top matrix has it if you exchange the 4th and 5th columns.)

Reduction: G&J point to a “private communication”, but I found a technical report by Lipski that explains the reduction.  The reduction is from Hamiltonian Path on cubic graphs (each vertex has degree at most 3).  So we start with a graph G=(V,E) where each vertex is degree 3 or less.  We construct a new graph G’=(V’,E’) where G’ adds new vertices and edges so that each vertex in V has degree 4.  Each new vertex has degree 1 (and so the new edges we add to V always connect to distinct new vertices).  Take the incidence matrix of this graph (as defined in the Consecutive Ones Submatrix problem) and use it as A.

If G has a Hamiltonian Path, then we can split A into two parts: the vertices in the path (thus, all of V) and everything else.  The Hamiltonian Path has the consecutive ones property, just like we saw in the Consecutive Ones Submatrix problem.  The other rows just map to disjoint paths of length 2 (two degree one edges connected by some vertex in V) so will be able to be rearranged.

If A has a partition that works, then choose some vertex v in V.  Suppose it ends up in A1.  We know that this vertex has degree 4.  We also know that to satisfy the consecutive ones property, v needs to be adjacent to exactly 2 things in A1 and 2 things in A2 for the consecutive ones property to work out.  The vertices in A1 need to form a chain of vertices all in V to make the consecutive ones property hold, so will form a Hamiltonian Path.

Difficulty: 6.  The paper glosses over a lot of detail, and I did to.  For example, the paper says “Without loss of generality we may assume that V ∈ M1” (the paper’s version of A1.  I don’t think it’s obvious at all that the entirety of V will end up all in one partition or the other.  I think it’s true, but I think it needs more work from a student to explain why it works.

Protected: Consecutive Ones Submatrix

This content is password protected. To view it please enter your password below:

Protected: 3-Matroid Intersection

This content is password protected. To view it please enter your password below:

Protected: Kth Shortest Path

This content is password protected. To view it please enter your password below:

Protected: Isomorphic Spanning Tree

This content is password protected. To view it please enter your password below:

Protected: Maximum Leaf Spanning Tree, Connected Dominating Set

This content is password protected. To view it please enter your password below:

Protected: Degree Constrained Spanning Tree

This content is password protected. To view it please enter your password below:

Protected: Hamiltonian Completion

This content is password protected. To view it please enter your password below: