(This question is inteneded for people who have heard of "Vertex Partitioning Problems" framework of Telle and Proskurowski. Others may dig in only if they are interested in practical algorithms for partial-$k$ trees.)

For solving problems in parital $k$-trees (i.e., graphs of bounded treewidth), the "Vertex Partitioning Problems" framework of Telle and Proskurowski looks promising. This framework gives practical algorithms for some problems (as opposed to MSO). Given a graph $G$ and a $q\times q$ matrix $D$ each entry of which is a subset of $\{0,1,2,\dots\}$, the question "Does there exist a partition $V_1, V_2, \dots ,V_q$ of $V(G)$ such that $\forall x \in V_i,\; |N(x) \cap V_j| \in D(i,j)$" is a vertex partitioning problem.

Their paper (Algorithms for vertex partitioning problems on partial k-trees) claim that every vertex partitioning problem is solvable in time polynomial for partial $k$-trees (time complexity is like $\mathcal{O}(nq^{2(k+1)})$

My doubt is regarding the "cofinite" condition they use. Is this important? Doesn't that mean this method doesn't work (out of box) for distance-2 coloring, since for distance-2 coloring the matrix $D$ must consist of entries $\{0\}$ along (main) diagonal and entries $\{0,1\}$ for off-diagonal.

Note: They explicitly state that the method works for coloring. For coloring also, diagonal entries are same; May be main diagonal is a special case?

Thank you.


distance-2 coloring is coloring in the square (d(x,y) <= 2 implies xy an edge in the square). If a graph has tw k, its square has bounded clique-width (see Gurski-Wanke and Suchan-Todinca). See Oum et al. for algorithms as in Proskurowski-Telle for graphs of bounded clique-width.

| cite | improve this answer | |
  • $\begingroup$ Thank you for pointing this out. But, I am afraid algorithms for bounded clique-width graph class will be more complicated, and have higher hidden constants as the class is so wide. In addition, I am not interested in distance-2 coloring per se.; I am largely interested in the power and limitations of their framework. $\endgroup$ – Cyriac Antony Jan 21 at 16:15
  • $\begingroup$ If you did have a look at the pointed papers you would see that what I said for $2$ is true for any fixed $l$. Also, the algorithms by Binh-Minh et al. are also singly exponential in the clique-width. If you want cases that do not work even for tree-width, you can have a look at this paper arxiv.org/abs/1004.2642 Sure, distance-$l$ colouring is moderately exponential for bounded clique-width as $G^l$ has clique-width at most $2(l+1)^{cw(G)}$, and $k$-colouring is a partitionning problem with $0$ on the diagonals and $\mathbb{N}$ in any other entry. $\endgroup$ – M. kanté Jan 22 at 8:40
  • $\begingroup$ Sorry, i mean i am interested in the "Vertex Partition Problem" framework $\endgroup$ – Cyriac Antony Jan 22 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.