arxiv: 2605.10487 · v1 · submitted 2026-05-11 · 🧮 math.CO

Recognition: no theorem link

Algorithm for finding vertex-edge domination number on graphs with bounded treewidth and related problems on planar graphs

Haixiang Zhang, Mei Lu, Yichen Wang

Pith reviewed 2026-05-12 04:33 UTC · model grok-4.3

classification 🧮 math.CO

keywords vertex-edge dominationtreewidthplanar graphsdynamic programmingNP-complete problemssubexponential algorithmsdominating sets

0 comments

The pith

Graphs with bounded treewidth admit a polynomial-time algorithm for computing the vertex-edge domination number.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a polynomial-time algorithm that computes a minimum vertex-edge dominating set on any graph whose treewidth is bounded by a fixed constant. It also proves that every planar graph G satisfies tw(G) = O(sqrt(gamma_ve(G))). This treewidth bound immediately supplies an O(c^sqrt(k) |V(G)|)-time algorithm for deciding whether a planar graph has ve-domination number at most k. The results extend tractability from the known linear-time case on trees to all bounded-treewidth graphs and to subexponential time on planar graphs.

Core claim

A polynomial-time algorithm exists for finding a minimum ve-dominating set on graphs with bounded treewidth. Moreover, the treewidth of a planar graph G with ve-domination number gamma_ve(G) is O(sqrt(gamma_ve(G))), which yields an O(c^sqrt(k) |V(G)|)-time algorithm for the k-ve-domination problem on planar graphs.

What carries the argument

Dynamic programming on tree decompositions whose states track which edges incident to the current bag are covered by the ve-domination rule.

If this is right

Minimum ve-dominating sets can be computed in linear time on trees and all other graphs of constant treewidth.
The k-ve-domination problem on planar graphs can be solved in time exponential only in the square root of k.
Any planar graph with small ve-domination number must also have small treewidth.
The same dynamic-programming tables decide the problem for every fixed treewidth bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The treewidth bound could be combined with known planar-separator techniques to obtain polynomial-time approximation schemes for ve-domination on planar graphs.
The same state-tracking idea may apply directly to other edge-covering domination variants on bounded-treewidth graphs.
Practical implementations on moderate-sized planar graphs would test whether the hidden constants in the O(c^sqrt(k) n) bound remain manageable.
If the constant hidden in O(sqrt(gamma_ve)) can be lowered, the subexponential algorithm for planar instances would become faster.

Load-bearing premise

The standard dynamic-programming framework on tree decompositions can be adapted to the ve-domination definition without introducing an extra exponential factor in the treewidth.

What would settle it

A graph of treewidth 5 on which no polynomial-time procedure computes the exact vertex-edge domination number, or a planar graph whose treewidth exceeds any fixed multiple of the square root of its ve-domination number.

Figures

Figures reproduced from arXiv: 2605.10487 by Haixiang Zhang, Mei Lu, Yichen Wang.

**Figure 1.** Figure 1: (Generalized) Upper Triples. Li is called s-non-vacuous if, for s = 1, Ci,j is non-vacuous, and for s > 1, inductively, there exists a (s − 1)-non-vacuous layer component from layer Li+1 in the interior of Ci,j (i.e., in the region enclosed by the subgraph induced by Ci,j ). So Ci,j is s-non-vacuous iff the corresponding component node in the layer decomposition has distance s − 1 to a leaf node. We have t… view at source ↗

**Figure 2.** Figure 2: (Generalized) Lower Triples [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

**Figure 4.** Figure 4: In either of these cases, the middle triple is defined as the set [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗

**Figure 4.** Figure 4: (Generalized) Middle Triples [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗

**Figure 5.** Figure 5: S ′ i separates Li−1 and Li+4 when y2 is dominated [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗

**Figure 7.** Figure 7: Construction of Step 6. (2) For each fixed 0 ≤ j ≤ t, assume {Gi1 , . . . , Gik } ={Gi | Gi connects Sj and Sj+1 or Gi only connects Sj+1 (except empty sets)}. In the tree-decomposition T , sequentially connect Sj , Ti1 , . . . , Tik , Sj+1. (3) For each 0 ≤ j ≤ t and {Gi1 , . . . , Gik } is defined as before. If N is a node of Til for some 1 ≤ l ≤ k, replace N by N′ = N ∪ Sj ∪ Sj+1. It is easy to verify T… view at source ↗

read the original abstract

Given a graph $G=(V,E)$, a vertex $u \in V$ {\em ve-dominates} all edges incident to any vertex of $N_G[u]$. A set $S \subseteq V$ is a {\em ve-dominating set} if for all edges $e\in E$, there exists a vertex $u\in S$ such that $u$ ve-dominates $e$. The minimum cardinality among all ve-dominating sets is known as the \textit{vertex-edge domination number} (or simply ve-domination number) and denoted by $\gamma_{ve}(G)$. Finding a minimum ve-dominating set was proved to be NP-complete. Restricted to trees, the problem admits a linear-time algorithm. Treewidth is a commonly used parameter for solving NP-hard problems. In this paper, we present a polynomial-time algorithm for finding a minimum ve-dominating set on graphs with bounded treewidth. Moreover, we show that the treewidth of a planar graph $G$ with ve-domination number $\gamma_{ve}(G)$ is $O(\sqrt{\gamma_{ve}(G)})$ and present an $O(c^{\sqrt{k}}|V(G)|)$-time algorithm for the $k$-ve-domination problem on planar graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a standard dynamic programming algorithm for minimum vertex-edge dominating sets on bounded-treewidth graphs plus an O(sqrt(gamma_ve)) treewidth bound for planar graphs.

read the letter

The main takeaway is that this work adapts treewidth dynamic programming to compute the vertex-edge domination number in polynomial time when treewidth is fixed, and it shows planar graphs satisfy tw(G) = O(sqrt(gamma_ve(G))), which immediately yields an O(c^sqrt(k) n) algorithm for deciding whether gamma_ve <= k on planar graphs. Both results follow from established techniques rather than new machinery. The DP tracks vertex selections in each bag together with the coverage status of incident edges via closed neighborhoods, which fits the local nature of the ve-domination definition without obvious extra exponential factors. The planar bound is obtained by relating a minimum ve-dominating set to a vertex cover and applying known separator theorems for planar graphs. This is a clean, incremental extension of prior results on other domination numbers. The paper does well by making the state definitions and the planar consequence explicit so that the algorithm can be implemented from the description. The claims line up with the literature on bounded-treewidth problems and do not introduce circular steps or invented parameters. The soft spots are limited to the usual ones for this style of paper. Without the full transition tables it is hard to verify the precise number of states per bag or to rule out a small hidden dependence on treewidth, though nothing in the outline suggests a problem. The constant hidden in the O(sqrt(gamma_ve)) bound also matters for the practical exponent in the planar algorithm, but the derivation itself appears standard. No load-bearing gaps or contradictions are visible. This paper is aimed at researchers who already work on parameterized algorithms for domination problems. A reader who needs a concrete algorithm or bound for the ve-variant on low-treewidth or planar graphs will find it directly useful. It is too specialized to interest a broad graph-theory audience. The work deserves a serious referee to check the DP details and the planar proof. I recommend sending it for peer review.

Referee Report

0 major / 1 minor

Summary. The manuscript presents a polynomial-time algorithm for computing a minimum vertex-edge dominating set on graphs of bounded treewidth via dynamic programming on tree decompositions. It further proves that any planar graph G satisfies tw(G) = O(√γ_ve(G)) and derives an O(c^√k |V(G)|)-time algorithm for the k-ve-domination problem on planar graphs.

Significance. If the claims hold, the work extends standard DP techniques for domination-type problems to the vertex-edge variant, yielding exact polynomial-time solutions on bounded-treewidth graphs and subexponential-time solutions on planar graphs. The constructive algorithmic results and the separator-based treewidth bound (once N[S] forms a vertex cover) are strengths that align with established methods in parameterized complexity.

minor comments (1)

[Abstract] Abstract: the running-time dependence on the treewidth bound w is not stated (e.g., whether the algorithm is O(n·f(w)) for some function f); adding this would improve clarity for readers familiar with treewidth results.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive recommendation to accept the manuscript and for the accurate summary of our results. We appreciate the recognition of the algorithmic contributions and the treewidth bound for planar graphs.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via standard techniques

full rationale

The paper's central claims are a constructive polynomial-time DP algorithm on tree decompositions for bounded-treewidth graphs (adapting standard bag-state tracking for ve-domination coverage) and a planar treewidth bound derived from the observation that N[S] forms a vertex cover for any ve-dominating set S, followed by known planar separator properties. Neither step reduces to a self-definition, fitted parameter renamed as prediction, or load-bearing self-citation; both rest on externally verifiable graph-theoretic facts and algorithmic frameworks that do not presuppose the target results. No equations or claims in the derivation chain are equivalent to their inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard dynamic-programming framework for bounded-treewidth graphs and basic properties of planar graphs; no new free parameters, invented entities, or ad-hoc axioms are introduced beyond domain assumptions.

axioms (2)

domain assumption Dynamic programming on a tree decomposition of width w solves the ve-domination problem in time polynomial in n but exponential in w.
The polynomial-time claim for bounded treewidth implicitly relies on this standard technique being adaptable to the ve-domination definition.
domain assumption Planar graphs admit tree decompositions whose width is O(sqrt of the solution size) for many covering problems.
The O(sqrt(γ_ve)) bound and the resulting algorithm extend known planar-graph techniques to this variant.

pith-pipeline@v0.9.0 · 5537 in / 1418 out tokens · 47797 ms · 2026-05-12T04:33:47.749081+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

Fixed parameter algorithms for dominating set and related problems on planar graphs.Algorithmica, 33:461–493, 2002

Alber, Bodlaender, Fernau, Kloks, and Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs.Algorithmica, 33:461–493, 2002

work page 2002
[2]

Alber and R

J. Alber and R. Niedermeier. Improved tree decomposition based algorithms for domination-like problems. InLatin American Symposium on Theoretical Informatics, pages 613–627. Springer, 2002

work page 2002
[3]

Arnborg, J

S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308–340, 1991

work page 1991
[4]

Z. Bai, J. Tu, and Y. Shi. An improved algorithm for the vertex coverP3 problem on graphs of bounded treewidth.Discrete Mathematics & Theoretical Computer Science, 21, 2019

work page 2019
[5]

B. S. Baker. Approximation algorithms for np-complete problems on planar graphs. Journal of the ACM (JACM), 41(1):153–180, 1994

work page 1994
[6]

H. L. Bodlaender. Treewidth: Algorithmic techniques and results. InInterna- tional Symposium on Mathematical Foundations of Computer Science, pages 19–36. Springer, 1997

work page 1997
[7]

H. L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth.Theo- retical computer science, 209(1-2):1–45, 1998

work page 1998
[8]

Boutrig, M

R. Boutrig, M. Chellali, T. W. Haynes, and S. T. Hedetniemi. Vertex-edge domination in graphs.Aequationes mathematicae, 90:355–366, 2016

work page 2016
[9]

Chiba, T

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using pq-trees.Journal of computer and system sciences, 30(1):54–76, 1985

work page 1985
[10]

Kloks.Treewidth: computations and approximations

T. Kloks.Treewidth: computations and approximations. Springer, 1994

work page 1994
[11]

Krishnakumari, Y

B. Krishnakumari, Y. B. Venkatakrishnan, and M. Krzywkowski. Bounds on the vertex–edge domination number of a tree.Comptes rendus mathematique, 352(5):363– 366, 2014

work page 2014
[12]

J. R. Lewis.Vertex-edge and edge-vertex parameters in graphs. Ph.D. thesis, Clemson University, 2007. 19

work page 2007
[13]

Paul and K

S. Paul and K. Ranjan. Results on vertex-edge and independent vertex-edge domi- nation.Journal of Combinatorial Optimization, 44(1):303–330, 2022

work page 2022
[14]

Peng and Y.-H

S.-L. Peng and Y.-H. Tsai. Roman domination on graphs of bounded treewidth. In Proceedings of the 24th Workshop on Combinatorial Mathematics and Computation Theory, pages 128–131. 2007

work page 2007
[15]

K. W. Peters Jr.Theoretical and algorithmic results on domination and connectivity (Nordhaus-Gaddum, Gallai type results, max-min relationships, linear time, series- parallel). Clemson University, 1986

work page 1986
[16]

Żyliński

P. Żyliński. Vertex-edge domination in graphs.Aequationes mathematicae, 93(4):735– 742, 2019. 20

work page 2019