This is my note on low-dimension linear programming & color refinement algorithms.

1 the problem & failed attempts

In September I’m working on the following small problem,

which is highly related to algorithms for linear programming in low dimensions.

This can be solve in $O(2^{2^d}(m+n))$ through Megiddo’s algorithm for multidimensional search problem. (see my slides)

I want to show that for general piecewise linear convex functions in ${\mathbb{R}}^d$, my problem can be formulated as a LP-type problem with low combinatorial dimension.

A failed attempt is trying to write $F={\sum }_i{f}_i$. However, there may be too many breakpoints on $F$. (see a previous post). Another possible way is using some dimension reduction techniques [1].

2 color refinement on matrices

I do not have high expectation on this method, since I need to show that color refinement indeed reduce the dimension from $n+d$ to $d$ and that the reduction can be done in linear time.

Given a initial coloring of vertices in a directed graph $G=(V,A)$, we want to compute the coarsest regular congruent coloring.

Colorings can be considered as equivalence relations on the vertices. An equivalence relation $R$ on $V$ is congruent if for all $u,v,w\in V$, [$(u,v)\in R$ and $(v,w)\in A$] implies that [$\exists v^{\prime }\in V$ such that $(v,v^{\prime })\in A$ and $(v^{\prime },w)\in R$]. Note that this coincides with the general definition of congruence relation in algebraic structures.(We can copy each vertex #outdegree times to make $A$ an unary operation.)

A coloring is regular if for any two vertices $u,v$, the number of successors in each color are the same. Consider two colorings $C_1,C_2$. $C_1$ is a refinement of $C_2$(or $C_2$ is coarser than $C_1$) if for any two vertices having the same color in $C_1$, they have the same color in $C_2$.

Basic Lemma 1 in [2] shows that the problem above is equivalent to the description in this wiki page.

The first quasilinear time algorithm for the color refinement problem on graphs is given in [2], and later in [3]. It is shown in [4] that $O((m+n)\log n)$ is the best possible running time. It is also shown in [5] that for any number of vertices there exists a graph which requires at least $n-2$ iterations to reach a stable coloring(note that the upperbound is $n-1$). See this for a nice survey on applications.

2.1 connections

2.1.1 color refinement on graphs $\to$ on matrices

Now we add edge weights on the directed graph. Suppose all arcs have weight 1. One can see that a congruent and regular coloring requires that two vertices have the same color iff for each color the total weight of arcs going to vertices in that color are the same. Slightly generalize this configuraton, we can consider arbitrary arc weights.

Now color refinement on matrices are almost the same as doing color refinement on the incidence matrix of a weighted digraph. However, not every matrix is square. For any matrix $A\in {\mathbb{R}}^{v\times w}$, we consider it as a bitartite graph $G=(V\bigsqcup W,A)$, where $|V|=v$ and $|W|=w$. Then $A_{ij}=w(i,j)$ if $(i,j)$ is an arc in $G$ and 0 otherwise.

2.1.2 color refinement on matrices $\to$ dimension reduction of LPs

This part is not intuitive and complicated. I think the ESA 14 paper [1] is very concise (compared to the arxiv version), however still takes four and a half pages to explain this part. So I will just briefly explain the idea.

This connection is based on an important theorem, stating that the color refinement of a matrix $A$ has strong relation with the fractional automorphism of $A$. To do the reduction, we first compute a color refinement of $A$. Based on the partitions of columns and rows of $A$ in the color refinement(partition matrices), we can conpute the factor matrix of $A$, denoted by $[A]$, which is small than $A$. Then finally, the authors proved a reduction lemma, which shows that the optimal solution to factor matrix of the entire LP(I don’t know the exact name, just the matrix one uses in the simplex method) is a linear mapping of the optimal solution of the original LP.

2.2 is it useful?

The reduction looks clever and has a wide application. However, as far as I know, it does nothing on my problem. I don’t think the matrix in my problem is special enough to allow color refinement algorithms run in linear time on it. Also color refinement does not necessarily partition all $f_i$ columns in one part. ¯\_(⊙︿⊙)_/¯

2.3 reflection

Multidimensional search is harder than LP-type problems, this question is no exception. Now there are three kinds of problems I am interested in.

1. Minimax parametric optimization
2. Multidimensional search problems
3. LP-type problems

What’s the connections among them?…

Now there are some important concrete problem in the intersections.

2.3.1 Euclidean one-centre problem

Dyer showed that this problem can be considered as a multidimensional search problem (in ${\mathbb{R}}^{d+1}$) in [6]. The conversion is not easy and not intuitive. Das et al. claimed that this problem is a LP-type problem with some additional constraints in [7]. It is still unknown whether it is possible to formulate the weighted Euclidean one-centre problem in ${\mathbb{R}}^d$ as a LP-type problem with combinatorial dimension $O(d)$ (which is quite surprising…)

2.3.2 Minimizing the sum of some pwl convex functions(my problem)

see above for the definition.

Clearly this is a minimax parametric optimization problem. Zemel also showed this is a multidimensional search problem with dimension $d$. We want to know that if this is a LP-type problem with combinatorial dimension $O(d)$…

It seems that recognizing LP-type is hard. A lecture on LP-type problems by David Eppstein.

Here are some materials for Low dimension LP:

• chapter 20 of Geometric Approximation Algorithms by Sariel Har-Peled. https://sarielhp.org/book/chapters/lp.pdf
• the fastest deterministic algorithm for this problem [8]
• my slides on Seidel’s $O(d!n)$ algorithm

References