2
$\begingroup$

This question is on "Vertex Partitioning Problems" framework of Telle and Proskurowski.

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jan 21, 2020 at 16:15
  • 1
    $\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é
    Commented Jan 22, 2020 at 8:40
  • $\begingroup$ Sorry, i mean i am interested in the "Vertex Partition Problem" framework $\endgroup$
    – Cyriac Antony
    Commented Jan 22, 2020 at 9:20
0
$\begingroup$

Thanks to M. kanté for pointing out further papers that studied this framework. Reading later papers that deal with vertex partioning problem framework (mostly under the name LS-VSP problems) resolved my confusion on "cofinite" condition.

Short answer: Distance-2 coloring fits in their framework. Every $\exists D_q$-problem in their framework admit FPT algorithm if each entry of the degree constraint matrix $D_q$ is either finite or cofinite.

Suppose $D_q$ is a $q\times q$ matrix with entries from $\mathbb{Z}^+$ (i.e., positive integers). A $\exists D_q$-problem in the vertex partitioning problem (also called LS-VSP problem) framework of Telle and Proskurowski takes a graph $G$ as input and asks whether the vertex set of $G$ can be partitioned into a $q$ sets $V_1,V_2,\dots,V_q$ such that for every pair $i,j$ with $i\neq j$, every vertex in $V_i$ has exactly $D_q(i,j)$ neighbors in $V_j$ (here, $D_q(i,j)$ denotes the $(i,j)^{th}$ entry of $D_q$).

In the first paper that introduced the framework, Telle and Proskurowski proved that every $\exists D_q$-problem admit an FPT algorithm with parameter treewidth provided every entry in $D_q$ is either finite or cofinite (importantly, this algorithm is not galactic unlike algorithms obtained from the MSO framework). Later, it was proved that such problems admit an FPT algorithm for various parameters including cliquewidth [1,2,3].

Another closely related but distinct framework is due to Gerber and Kobler[4] (problems in this framework also admit FPT algorithm with parameter cliquewidth). A $\exists D_q$-problem fits in both frameworks if every entry in $D_q$ is a set of consecutive integers.

In general, there are good algorithmic techniques to produce efficient FPT algorithms for $\exists D_q$-problem in various classes if $q$ as well as $\max\{|A| : A\text{ is a finite entry in }D_q\}$ and $\max\{|\mathbb{Z}^+\setminus B| : B\text{ is a cofinite entry in }D_q\}$ are small.

Most of these papers also provide FPT algorithms (and/or poly. time algorithm in restricted classes) for optimization versions of $\exists D_q$-problems (i.e., minimize/maximize $q$, the number of parts in the partitions).

References

[1] Oum, Sang-il; Sæther, Sigve Hortemo; Vatshelle, Martin, Faster algorithms for vertex partitioning problems parameterized by clique-width, Theor. Comput. Sci. 535, 16-24 (2014). ZBL1419.05204.

[2] Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin, Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems, Theor. Comput. Sci. 511, 66-76 (2013). ZBL1408.68111.

[3] Belmonte, Rémy; Vatshelle, Martin, Graph classes with structured neighborhoods and algorithmic applications, Theor. Comput. Sci. 511, 54-65 (2013). ZBL1408.68109.

[4] Gerber, Michael U.; Kobler, Daniel, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Theor. Comput. Sci. 299, No. 1-3, 719-734 (2003). ZBL1042.68092.

[5] Telle, J. A. (1994). Vertex partitioning problems: characterization, complexity and algorithms on partial k-trees, Doctoral thesis(1994), University of Oregon.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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