<p>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 &quot;cofinite&quot; condition.</p>
<p><strong>Short answer: Distance-2 coloring fits in their framework. Every <span class="math-container">$\exists D_q$</span>-problem in their framework admit FPT algorithm if each entry of the degree constraint matrix <span class="math-container">$D_q$</span> is either finite or cofinite.</strong></p>
<p>Suppose <span class="math-container">$D_q$</span> is a <span class="math-container">$q\times q$</span> matrix with entries from <span class="math-container">$\mathbb{Z}^+$</span> (i.e., positive integers). A <span class="math-container">$\exists D_q$</span>-problem in the vertex partitioning problem (also called LS-VSP problem) framework of Telle and Proskurowski takes a graph <span class="math-container">$G$</span> as input and asks whether the vertex set of <span class="math-container">$G$</span> can be partitioned into a <span class="math-container">$q$</span> sets <span class="math-container">$V_1,V_2,\dots,V_q$</span> such that for every pair <span class="math-container">$i,j$</span> with <span class="math-container">$i\neq j$</span>, every vertex in <span class="math-container">$V_i$</span> has exactly <span class="math-container">$D_q(i,j)$</span> neighbors in <span class="math-container">$V_j$</span> (here, <span class="math-container">$D_q(i,j)$</span> denotes the <span class="math-container">$(i,j)^{th}$</span> entry of <span class="math-container">$D_q$</span>).</p>
<p>In the first paper that introduced the framework, Telle and Proskurowski proved that every <span class="math-container">$\exists D_q$</span>-problem admit an FPT algorithm with parameter treewidth provided every entry in <span class="math-container">$D_q$</span> 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].</p>
<p>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 <span class="math-container">$\exists D_q$</span>-problem fits in both frameworks if every entry in <span class="math-container">$D_q$</span> is a set of consecutive integers.</p>
<p>In general, there are good algorithmic techniques to produce efficient FPT algorithms for <span class="math-container">$\exists D_q$</span>-problem in various classes if <span class="math-container">$q$</span> as well as <span class="math-container">$\max\{|A| : A\text{ is a finite entry in }D_q\}$</span> and <span class="math-container">$\max\{|\mathbb{Z}^+\setminus B| : B\text{ is a cofinite entry in }D_q\}$</span> are small.</p>
<p>Most of these papers also provide FPT algorithms (and/or poly. time algorithm in restricted classes) for optimization versions of <span class="math-container">$\exists D_q$</span>-problems (i.e., minimize/maximize <span class="math-container">$q$</span>, the number of parts in the partitions).</p>
<h2>References</h2>
<p>[1] <em>Oum, Sang-il; Sæther, Sigve Hortemo; Vatshelle, Martin</em>, <a href="http://dx.doi.org/10.1016/j.tcs.2014.03.024" rel="nofollow noreferrer"><strong>Faster algorithms for vertex partitioning problems parameterized by clique-width</strong></a>, Theor. Comput. Sci. 535, 16-24 (2014). <a href="https://zbmath.org/?q=an:1419.05204" rel="nofollow noreferrer">ZBL1419.05204</a>.</p>
<p>[2] <em>Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin</em>, <a href="http://dx.doi.org/10.1016/j.tcs.2013.01.009" rel="nofollow noreferrer"><strong>Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems</strong></a>, Theor. Comput. Sci. 511, 66-76 (2013). <a href="https://zbmath.org/?q=an:1408.68111" rel="nofollow noreferrer">ZBL1408.68111</a>.</p>
<p>[3] <em>Belmonte, Rémy; Vatshelle, Martin</em>, <a href="http://dx.doi.org/10.1016/j.tcs.2013.01.011" rel="nofollow noreferrer"><strong>Graph classes with structured neighborhoods and algorithmic applications</strong></a>, Theor. Comput. Sci. 511, 54-65 (2013). <a href="https://zbmath.org/?q=an:1408.68109" rel="nofollow noreferrer">ZBL1408.68109</a>.</p>
<p>[4] <em>Gerber, Michael U.; Kobler, Daniel</em>, <a href="http://dx.doi.org/10.1016/S0304-3975(02)00725-9" rel="nofollow noreferrer"><strong>Algorithms for vertex-partitioning problems on graphs with fixed clique-width.</strong></a>, Theor. Comput. Sci. 299, No. 1-3, 719-734 (2003). <a href="https://zbmath.org/?q=an:1042.68092" rel="nofollow noreferrer">ZBL1042.68092</a>.</p>
<p>[5] Telle, J. A. (1994). <a href="http://www.ii.uib.no/%7Etelle/bib/Tth.pdf" rel="nofollow noreferrer"><strong>Vertex partitioning problems: characterization, complexity and algorithms on partial k-trees</strong></a>, Doctoral thesis(1994), University of Oregon.</p>

CC BY-SA 4.0
2021-01-02T03:59:17.263Z
2021-01-02T05:15:44.237Z
2021-01-02T05:15:44.237Z
Cyriac Antony
<p>distance-2 coloring is coloring in the square (d(x,y) &lt;= 2 implies xy an edge in the square). If a graph has tw k, its square has bounded clique-width (see <a href="https://www.sciencedirect.com/science/article/pii/S0166218X08004022?via%3Dihub" rel="nofollow noreferrer">Gurski-Wanke</a> and <a href="https://www.sciencedirect.com/science/article/pii/S0166218X07000601?via%3Dihub" rel="nofollow noreferrer">Suchan-Todinca</a>). See <a href="https://www.sciencedirect.com/science/article/pii/S0304397514002461?via%3Dihub" rel="nofollow noreferrer">Oum et al.</a> for algorithms as in Proskurowski-Telle for graphs of bounded clique-width. </p>

CC BY-SA 4.0
2020-01-21T16:15:29.287Z
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.
Cyriac Antony
CC BY-SA 4.0
2020-01-22T08:40:44.380Z
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 https://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.
M. kanté
CC BY-SA 4.0
2020-01-22T09:20:07.530Z
Sorry, i mean i am interested in the "Vertex Partition Problem" framework
Cyriac Antony
CC BY-SA 4.0
2020-01-21T08:13:37.633Z
2020-01-21T08:13:37.633Z
M. kanté
<p>This question is on &quot;Vertex Partitioning Problems&quot; framework of Telle and Proskurowski.</p>
<p>For solving problems in parital <span class="math-container">$k$</span>-trees (i.e., graphs of bounded treewidth), the &quot;Vertex Partitioning Problems&quot; framework of Telle and Proskurowski looks promising. This framework gives <em>practical</em> algorithms for some problems (as opposed to MSO). Given a graph <span class="math-container">$G$</span> and a <span class="math-container">$q\times q$</span> matrix <span class="math-container">$D$</span> each entry of which is a subset of <span class="math-container">$\{0,1,2,\dots\}$</span>, the question &quot;Does there exist a partition <span class="math-container">$V_1, V_2, \dots ,V_q$</span> of <span class="math-container">$V(G)$</span> such that <span class="math-container">$\forall x \in V_i,\; |N(x) \cap V_j| \in D(i,j)$</span>&quot; is a vertex partitioning problem.</p>
<p>Their paper (<a href="https://epubs.siam.org/doi/abs/10.1137/S0895480194275825" rel="nofollow noreferrer">Algorithms for vertex partitioning problems on partial k-trees</a>) claim that every vertex partitioning problem is solvable in time polynomial for partial <span class="math-container">$k$</span>-trees (time complexity is like <span class="math-container">$\mathcal{O}(nq^{2(k+1)})$</span></p>
<p>My doubt is regarding the &quot;<strong>cofinite</strong>&quot; 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 <span class="math-container">$D$</span> must consist of entries <span class="math-container">$\{0\}$</span> along (main) diagonal and entries <span class="math-container">$\{0,1\}$</span> for off-diagonal.</p>
<p>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?</p>
<p>Thank you.</p>

<graph-algorithms><graph-colouring><treewidth>
Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?
Cyriac Antony
# Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

(Asked by: username_0 on 2020-01-20)

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](https://epubs.siam.org/doi/abs/10.1137/S0895480194275825)) 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.

**Tags:** graph-algorithms, graph-colouring, treewidth

---

## 2 answers

### Answer by username_0 on 2021-01-02. Score: 0 | Accepted answer

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**](http://dx.doi.org/10.1016/j.tcs.2014.03.024), Theor. Comput. Sci. 535, 16-24 (2014). [ZBL1419.05204](https://zbmath.org/?q=an:1419.05204).

[2] *Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin*, [**Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems**](http://dx.doi.org/10.1016/j.tcs.2013.01.009), Theor. Comput. Sci. 511, 66-76 (2013). [ZBL1408.68111](https://zbmath.org/?q=an:1408.68111).

[3] *Belmonte, Rémy; Vatshelle, Martin*, [**Graph classes with structured neighborhoods and algorithmic applications**](http://dx.doi.org/10.1016/j.tcs.2013.01.011), Theor. Comput. Sci. 511, 54-65 (2013). [ZBL1408.68109](https://zbmath.org/?q=an:1408.68109).

[4] *Gerber, Michael U.; Kobler, Daniel*, [**Algorithms for vertex-partitioning problems on graphs with fixed clique-width.**](http://dx.doi.org/10.1016/S0304-3975(02)00725-9), Theor. Comput. Sci. 299, No. 1-3, 719-734 (2003). [ZBL1042.68092](https://zbmath.org/?q=an:1042.68092).

[5] Telle, J. A. (1994). [**Vertex partitioning problems: characterization, complexity and algorithms on partial k-trees**](http://www.ii.uib.no/%7Etelle/bib/Tth.pdf), Doctoral thesis(1994), University of Oregon.


---

### Answer by username_1 on 2020-01-21. Score: 4

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](https://www.sciencedirect.com/science/article/pii/S0166218X08004022?via%3Dihub) and [Suchan-Todinca](https://www.sciencedirect.com/science/article/pii/S0166218X07000601?via%3Dihub)). See [Oum et al.](https://www.sciencedirect.com/science/article/pii/S0304397514002461?via%3Dihub) for algorithms as in Proskurowski-Telle for graphs of bounded clique-width.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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 https://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.  
> **username_0**: Sorry, i mean i am interested in the "Vertex Partition Problem" framework  

---

