Computing L(p,1)-Labeling with Combined Parameters

NEW

Problem: For fixed $p\ge 1$, the standard decision form of $L(p,1)$-LABELING is:

Given a finite simple graph $G$ and an integer span bound $K$, decide whether there is

$$f:V(G)\to \{0,\dots,K-1\}$$

such that

$$uv\in E(G)\Rightarrow |f(u)-f(v)|\ge p, \qquad \operatorname{dist}_G(u,v)=2\Rightarrow f(u)\ne f(v).$$

The parameter is the twin-cover number $\operatorname{tc}(G)$. A twin cover $X\subseteq V(G)$ is a set such that every edge not incident with $X$ has twin endpoints.

The reconstructed open question is: for every fixed $p$, is $L(p,1)$-LABELING fixed-parameter tractable parameterized only by $\operatorname{tc}(G)$? This is the natural reading of the paper’s notation $L(p,1)$, where $p$ is fixed. If $p$ is instead encoded as an unparameterized part of the input, that is a stronger different formalization.

Result: Yes. For every fixed $p$, $L(p,1)$-LABELING is FPT parameterized by twin-cover number alone.

Sketch of the full algorithm.

Let $X$ be a twin cover of size $t$. It is known that such an $X$ can be found in FPT time, or we may take it as supplied.

Each component of $G-X$ is a clique whose vertices have the same neighborhood $A\subseteq X$. Call $A$ its type. There are at most $2^t$ types. For a nonempty type $A$, let its clique sizes be

$$s_{A,1}\ge s_{A,2}\ge\cdots,$$

let

$$n_A=\sum_i s_{A,i},$$

and for $1\le q<p$ let

$$d_A(q)=\sum_{i=1}^q s_{A,i},$$

missing terms being $0$.

For type $A\neq\varnothing$, labels used by all vertices of type $A$ must be distinct, because any two such vertices in different cliques are at distance $2$ through a vertex of $A$. A set $P_A$ of labels can label all cliques of type $A$ iff:

1. $|P_A|=n_A$;
2. for each $1\le q<p$, $P_A$ contains $q$ disjoint $p$-separated subsets of total size at least $d_A(q)$.

This is exactly the Greene–Kleitman chain-packing criterion applied to the poset on labels where $a<b$ iff $b-a\ge p$. The width of this poset is at most $p$, so only $q<p$ gives nontrivial inequalities.

Now build a finite alphabet depending only on $t,p$. A symbol at label position $\ell$ records:

• which vertices of $X$ receive label $\ell$;
• which nonempty outside types $A$ use label $\ell$;
• for each $A$ and $1\le q<p$, optional witness marks showing membership in one of the $q$ $p$-separated witness chains.

The alphabet forbids same-label conflicts: intersecting outside types cannot both appear; vertices/types at distance $2$ cannot share a label; adjacent objects cannot share a label. A finite automaton, remembering the previous $p-1$ symbols, enforces all distance-$<p$ adjacency constraints and all witness-chain $p$-separation constraints.

Then impose only Parikh/count constraints:

• each $x\in X$ appears exactly once;
• each nonempty type $A$ appears exactly $n_A$ times;
• for each $A$ and $q<p$, the total number of $q$-witness marks is at least $d_A(q)$;
• the word length is $K$.

Existence of a word accepted by a fixed finite automaton with fixed-dimensional Parikh constraints is decidable in FPT time by reducing to fixed-dimensional integer programming: use variables for transition counts of the automaton and apply Lenstra’s algorithm. The number of states, symbols, and variables depends only on $t,p$, not on clique sizes or $K$.

Empty type $A=\varnothing$ components are disconnected from the rest and from each other, so they only require

$$K\ge 1+p(s_{\max}-1),$$

where $s_{\max}$ is the largest empty-type clique size.

Correctness follows both ways:

• Any valid labeling gives such a word; for each $A,q$, mark the labels of the $q$ largest cliques of type $A$.
• Any accepted word gives label sets $P_A$; Greene–Kleitman then partitions each $P_A$ into chains of sizes $s_{A,i}$, which label the cliques of type $A$. The automaton guarantees all constraints involving $X$ and all equality conflicts between types.

Thus the decision problem is solvable in time

$$F(t,p)\cdot \operatorname{poly}(|G|+\log K).$$

For fixed $p$, this is FPT in $\operatorname{tc}(G)$ alone. The optimization version follows by binary search using the trivial upper bound $1+p(|V(G)|-1)$.

Citation: The open question is from Hanaka, Kawai, and Ono, “Computing $L(p,1)$-Labeling with Combined Parameters,” arXiv:2009.10502. The proof uses the Greene–Kleitman chain theorem and Lenstra’s fixed-dimensional integer programming theorem; twin covers are from Ganian, “Twin-cover: Beyond vertex cover in parameterized algorithmics.”