On the maximum number of minimal connected dominating sets in convex bipartite graphs

Mohamed Yosri Sayadi

REVIEW 4 major objections 5 minor 20 references

On the maximum number of minimal connected dominating sets in convex bipartite graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every convex bipartite graph on n vertices has at most O(1.7254^n) minimal connected dominating sets, and the paper gives an algorithm that lists them all in O(1.7254^n) time.

desk verdict Promising new upper bound for convex bipartite graphs, but the proof is too sketchy to certify as written. read the letter →

arxiv 1908.02174 v1 pith:SRZG72MZ submitted 2019-08-06 cs.DS cs.DMmath.CO

Mohamed Yosri Sayadi This is my paper · ORCID

classification cs.DScs.DMmath.CO MSC 05C6905C8568Q25

keywords minimalconnecteddominatingsetconvexbipartitegraphenumerationalgorithminput-sensitiveexactexponentialbranchingvectorintervalrepresentationlowerbound

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves a worst-case enumeration bound for a structured class of bipartite graphs: every convex bipartite graph on n vertices has at most O(1.7254^n) minimal connected dominating sets, and all of them can be listed in O(1.7254^n) time. The class is the first nontrivial bipartite family for which such an algorithm is known; for bipartite graphs in general, the best input-sensitive algorithms were previously no better than the general-graph bound. The proof exploits convexity, meaning one side of the bipartition can be ordered so that each vertex on the other side has a consecutive interval of neighbors, to keep the search tree small. It is complemented by a construction of convex bipartite graphs with at least $3^{{(n-2)/3}}$ such sets.

What carries the argument

The central object is the interval representation of a convex bipartite graph: fix an ordering of W so that every u in U has neighbors forming one consecutive interval Iu. On top of this representation, Lemma 6 is the load-bearing structural fact: for two selected U-vertices i,j with intersecting intervals, at most one further selected U-vertex can have its interval contained in the union Ii \cup Ij. This lemma bounds the branching in EnumLevel2 Step 6 and justifies the stop rules in EnumLevel3, and together with the final interval-hitting stage it yields the branching number below 1.7254.

What would settle it

Search for a convex bipartite graph with a minimal connected dominating set D containing i,j,k,l such that Ii \cap Ij is nonempty and both Ik and Il are contained in Ii \cup Ij; such an instance would falsify Lemma 6 and invalidate the branching analysis. A weaker empirical check is to enumerate all minimal connected dominating sets in large random convex bipartite graphs and look for a count exceeding 1.7254^n.

Watch

Extended reading notes

Core claim

Theorem 7 is the central claim: in a convex bipartite graph, the number of minimal connected dominating sets is O(1.7254^n), and the sets can be enumerated in time O(1.7254^n). The algorithm first fixes the U-side of a solution by a branching procedure whose worst-case branching vector stays below 1.7254, then completes the solution by selecting W-vertices that hit a family of required intervals. The paper also proves a complementary lower bound: a family of convex bipartite graphs has $3^{{(n-2)/3}}$ minimal connected dominating sets, so the maximum number is exponential with base between $3^{{1/3}}$ \approx 1.4422 and 1.7254, improving on the general-graph state of the art for this class.

Load-bearing premise

The result rests on Lemma 6: once two selected U-vertices have overlapping neighbor intervals, at most one other selected U-vertex can have its interval inside their union; if that lemma or its ordering argument fails, the branching vector and the O(1.7254^n) bound do not follow.

Editorial extensions

If this is right

Every n-vertex convex bipartite graph has at most O(1.7254^n) minimal connected dominating sets.
All minimal connected dominating sets of a convex bipartite graph can be enumerated in O(1.7254^n) time.
For convex bipartite graphs this replaces the best known general-graph input-sensitive bound, which is only of the form O(2^{(1-\epsilon)n}) with an extremely small \epsilon.
The lower-bound construction gives convex bipartite graphs with at least 3^{(n-2)/3} minimal connected dominating sets, so the upper bound is complemented by an exponential lower bound with base about 1.4422.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same interval-nesting mechanism could be tried on chordal bipartite graphs, for which no input-sensitive enumeration better than the general bound is known; an analogue of Lemma 6 there would likely give a similar exponential constant.
The gap between 3^{1/3} \approx 1.4422 and 1.7254 suggests two possible routes to a tighter constant: refining the EnumLevel2 branching vector, or constructing lower-bound families with larger base.
The final interval-hitting stage is generic enough that it may also enumerate minimal dominating sets or maximal irredundant sets in convex bipartite graphs, both problems the paper leaves open.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline: this paper has a plausible new result—an O(1.7254^n) upper bound and matching-ish enumeration algorithm for minimal connected dominating sets in convex bipartite graphs, plus a 3^{(n-2)/3} lower bound. The lower bound is a standard construction, and the upper bound approach fits with known measure-and-conquer work. If correct, it fills a real gap in the landscape, since bipartiteness is usually hard to exploit.

The paper does useful things well. The structural lemmas leading to the algorithm are sensible. Observation 2 and Lemmas 1–4 establish the basic properties of minimal connected dominating sets in convex bipartite graphs. The algorithm’s high-level plan—choose vertices in U first, then complete with W, using intervals to prune—is coherent. The lower bound construction is correct (though the convexity argument relies on a missing figure; that’s a minor presentation issue, easily fixed).

The soft spots are real and they sit exactly where the reader’s report says. Lemma 6 is load-bearing: it limits the number of U-vertices whose intervals lie inside the union of two intersecting intervals. The proof as written is too sketchy. After fixing an endpoint order, it simply states that k and l are cut vertices and then invokes vertices wx, wx' whose existence and relative order are not derived. The containment assertion used in Stage 2 Step 6—that every x in D∩N(r)\ {u,j} has Ix⊂(Iu∪Ij)—is also stated without proof. If that assertion fails, the branching vector bounding for deg(r)≥3 falls apart, and the 1.7254^n bound is not established.

The running-time analysis has the same disease. The branching vector for Step 6 is asserted as 'straightforward to see' and the vector itself is written ambiguously (t, t+1, ..., t+1, 1). A careful argument is needed to show that the worst case is when all neighbors of r are branched with a single forbidden vertex. The correctness invariant of the four stages is never stated precisely, so it’s hard to verify that the pruning rules don’t discard valid solutions.

None of this looks fatal. The approach is credible and the missing pieces appear to be fillable. But the current text does not contain enough detail for a referee to certify the theorem.

My bottom line: this deserves serious peer review. A good referee will either fix the gaps or uncover a real flaw. I would not cite it in its current state; I’d wait for a revised version. It’s worth bringing to a reading group for the technique, if people are interested in exact exponential algorithms.

Recommendation: send to a journal with a request for major revision before acceptance.

Referee Report

4 major / 5 minor

Summary. The paper studies the maximum number and enumeration of minimal connected dominating sets (MCDS) in convex bipartite graphs. It proposes a four-stage branching algorithm: EnumLevel1 selects the unique U-neighbor of w1; EnumLevel2 branches on U-vertices using the rightmost selected interval and Lemma 6 to restrict the number of selected U-neighbors of a W-vertex r; EnumLevel3 filters partial solutions using degree conditions on the interval representation; EnumLevel4 selects W-vertices from a set of interval constraints J. A measure-and-conquer analysis with measure |U|+|W\F| claims a worst-case branching number below 1.7254, giving the main theorem (Theorem 7): O(1.7254^n) MCDS and O(1.7254^n) enumeration time. A lower bound construction yields 3^{(n-2)/3} MCDS, matching the known general-graph lower bound.

Significance. If the technical gaps identified below can be closed, the result is a valuable contribution: it is the first input-sensitive enumeration bound for minimal connected dominating sets in a nontrivial bipartite subclass, and the upper bound O(1.7254^n) is substantially better than the best known general bound while being reasonably close to the lower bound 3^{(n-2)/3}≈1.4422^n. The algorithm is parameter-free, uses no fitted constants, and the lower-bound construction is simple and explicit. The claimed constants are derived within the standard Fomin–Kratsch branching framework rather than by numerical fitting. However, the paper currently does not supply a complete correctness proof, and the proof of the key structural lemma is partially asserted rather than derived; these are load-bearing gaps rather than presentation issues.

major comments (4)

[Section 3, Lemma 6] Lemma 6 is load-bearing for the Step 6 branching rule and for the Stage 3 stop rule when deg(r)>3, but the proof as written is not rigorous. After the endpoint ordering, the proof states 'It is clear that k,l are cut vertices' and then posits W-vertices w_x, w_x', w_y, w_y' with various separation properties; the inequalities w_y<l(I_j) and w_x'>r(I_i) are introduced without derivation. In particular, the proof never shows that the required vertices exist in D∩I_k and D∩I_l with the claimed component structure. A complete proof should establish, from the interval representation and Lemmas 1, 2, and 5, that a vertex k with I_k strictly contained in I_i∪I_j can be a cut vertex only if it has W-neighbors outside the intervals of all other selected U-vertices, and that two such vertices k,l would create a path contradicting the endpoint order. Without this argument, the assertion |N(r)∩D\{u,j}|≤1 in Section 4 Step 6 is unsupported.
[Section 4, Step 6 and Section 5, running-time analysis] The branching analysis of Step 6 is asserted rather than derived. The text says 'It is straightforward to see' that the worst case is |I_u∩I_j|=1 and no x with I_x⊆I_j, yielding the vector (t,t+1,...,t+1,1), but no proof is supplied. The containment assertion 'for any x∈D∩N(r)\{{u,j}} we have I_x⊂(I_u∪I_j)' is also stated without proof; it can be derived from Lemma 1 and the maximality of j's right endpoint, but the derivation should be written out. For the branching vector, the paper should explicitly compute the measure decreases: branch (i) removes all of N(r) (decrease t), each branch (ii) removes N(r) and forbids I_j∩I_u (decrease at least t+1), and branch (iii) removes only j (decrease 1), and should then prove that configurations with I_x⊆I_j or with a larger intersection are majorized by the vector (3,4,4,1). As it stands, the claimed bound α6<1.7254 is not justified.
[Section 4 (all stages)] The paper never states or proves a correctness theorem for the enumeration algorithm. There is no formal invariant relating a partial solution (D,T,F) to the set of minimal connected dominating sets that extend it, no proof that every MCDS is generated by at least one leaf of the search tree, no proof that every leaf output is an MCDS, and no discussion of duplicate outputs. The pruning decisions in Stage 3 (the deg(r)>3 stop, the deg(r)=2 interval-intersection update, and the deg(r)=3 constraints added to J) are described only by informal arguments. Since the central claim is an enumeration bound, soundness and completeness of the algorithm are as important as the branching analysis; both need to be stated as lemmas or as a theorem with proofs.
[Section 6, Proposition 1] The lower-bound graph is claimed to be convex bipartite, but the proof ends with 'It remains to observe that G is convex bipartite from its following model' and no explicit interval representation is given; the figure labels intervals I_u and I_v but the ordering of the W-vertices and the neighbor intervals of the U-vertices are not specified. Since convexity is the defining property of the class, this must be demonstrated: give the ordering of W and the interval for every U-vertex, or a precise description from which the ordering is evident. In addition, the characterization of the MCDS of this graph ('if and only if u,v∉D and |D∩T_i|=1') is asserted without proof; a short proof of minimality and completeness should be included.

minor comments (5)

[Section 3, Lemma 3 proof] The edge sets E' and E'' are never defined; they should be defined as the edge sets of the induced subgraphs on (U',W') and (U'',W''). Also, the phrase 'there is no w_j u∈E' is ambiguous because w_j denotes both the vertex and its index.
[Section 3, Lemmas 5 and 6] The notation I_k⊂{I_i∪I_j} should be I_k⊂I_i∪I_j; as written it suggests an element of a set of intervals. Several occurrences of 'It is clear' in the proofs should be replaced by explicit arguments, especially where the existence of specific W-vertices is asserted.
[Section 5, running-time analysis] The typeset branching vector contains LaTeX artifacts ('/bracehtipupleft ...'); in the final version use standard notation such as (t, underbrace{t+1,...,t+1}_{t-1}, 1).
[Section 6, Proposition 1] The figure should be described in the caption or text; the interval representation is not self-explanatory, and the interval for each U-vertex (x_i, y_i, z_i) should be listed or described.
[Section 4, EnumLevel4] The paper does not discuss how duplicate solutions are handled by EnumLevel4; if the search tree can reach the same output set via different branches, a deduplication argument or another mechanism should be stated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convex-bipartite upper bound is derived from structural lemmas and a measure-and-conquer branching analysis, and the lower bound is a direct construction.

full rationale

The paper's central claim, O(1.7254^n) minimal connected dominating sets in convex bipartite graphs, is obtained by a branching algorithm whose running-time bound is derived from standard measure-and-conquer recurrences with explicit branching vectors (Section 5). No parameter is fitted to a data subset and then renamed a prediction; the branching vectors are computed from the algorithm's reduction and branching rules. The structural lemmas in Section 3, including Lemma 6, are stated as combinatorial facts about minimal connected dominating sets in convex bipartite graphs, not as consequences of the theorem being proved. Even if Lemma 6's proof contains gaps, that is a correctness issue rather than circularity: the lemma is not assumed from the theorem nor imported from a self-citation. The lower bound (Proposition 1) is a direct construction with a computed count of 3^k = 3^{(n-2)/3} minimal connected dominating sets and an explicit convex bipartite interval model; it does not rely on the upper bound. Citations to prior work are used for background, known general lower bounds, and the measure-and-conquer framework, not as load-bearing self-citations. The paper is therefore self-contained against external benchmarks: its lower and upper bounds are independent, and no claim reduces by definition to an input assumption.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No parameters are fitted; the paper is a self-contained combinatorial derivation. The main external inputs are the interval-order definition, the branching-analysis framework, and the known lower-bound construction. The missing figure for the convexity of the lower-bound graph is an unproved premise.

assumptions (3)

domain assumption The input graph is convex bipartite with the W-ordering given by the interval representation.
Every lemma and algorithm stage assumes the interval ordering of W from Section 2.
standard math The measure-and-conquer branching framework of Fomin and Kratsch [16] correctly converts branching vectors into O*(alpha^n) leaf bounds.
The upper bound is derived entirely through this external framework; no proof of the framework is repeated.
ad hoc to paper The graph constructed in Proposition 1 has a valid convex bipartite interval representation.
The text says convexity follows from a model, but the model/figure is missing and convexity is asserted rather than shown.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the maximum number of minimal connected dominating sets in convex bipartite graphs." pith.science (2026). https://pith.science/paper/SRZG72MZ

@misc{pith2026190802174,
  author       = {Pith},
  title        = {Pith review of: On the maximum number of minimal connected dominating sets in convex bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SRZG72MZ}},
  note         = {Machine review of arXiv:1908.02174}
}

abstract

The enumeration of minimal connected dominating sets is known to be notoriously hard for general graphs. Currently, it is only known that the sets can be enumerated slightly faster than $\mathcal{O}^{*}(2^n)$ and the algorithm is highly nontrivial. Moreover, it seems that it is hard to use bipartiteness as a structural aide when constructing enumeration algorithms. Hence, to the best of our knowledge, there is no known input-sensitive algorithm for enumerating minimal dominating sets, or one of their related sets, in bipartite graphs better than that of general graphs. In this paper, we provide the first input-sensitive enumeration algorithm for some non trivial subclass of bipartite graphs, namely the convex graphs. We present an algorithm to enumerate all minimal connected dominating sets of convex bipartite graphs in time $\mathcal{O}(1.7254^{n})$ where $n$ is the number of vertices of the input graph. Our algorithm implies a corresponding upper bound for the number of minimal connected dominating sets for this graph class. We complement the result by providing a convex bipartite graph, which have at least $3^{(n-2)/3}$ minimal connected dominating sets.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 15 canonical work pages

[1]

Below all subsets for minimal connected dominating set

Daniel Lokshtanov, Michal Pilipczuk, and Saket Saurabh. Below all subsets for minimal connected dominating set. SIAM J. Discrete Math. , 32(3):2332--2345, 2018

work page 2018
[2]

P. A. Golovach, P. Heggernes, D. Kratsch, Enumerating minimal connected dominating sets in graphs of bounded chordality , Theor. Comput. Sci. 630 (2016) 63--75

work page 2016
[3]

F. N. Abu-Khzam, A. E. Mouawad, M. Liedloff, An exact algorithm for connected red-blue dominating set, J. of Discrete Algorithms 9 (3) (2011) 252--262

work page 2011
[4]

Skjørten, I.B.: Faster enumeration of minimal connected dominating sets in split graphs (2017)

work page 2017
[5]

Damaschke, P., M \" u ller, H., Kratsch, D.: Domination in convex and chordal bipartite graphs. Inf. Process. Lett. 36(5), 231--236 (1990), https://doi.org/10.1016/0020-0190(90)90147-P

work page doi:10.1016/0020-0190(90)90147-p 1990
[6]

Bang-jensen, J., Huang, J., Macgillivray, G., Yeo, A.: Domination in convex bipartite and convex-round graphs (1999)

work page 1999
[7]

Hedetniemi J

S.T. Hedetniemi J. Pfaff, R. Laskar. NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical Report 428, Department of Mathematical Sciences, Clemenson University , 1983

work page 1983
[8]

The NP-completeness of steiner tree and dominating set for chordal bipartite graphs

Haiko Müller and Andreas Brandstädt. The NP-completeness of steiner tree and dominating set for chordal bipartite graphs. Theoretical Computer Science , 53(2):257 -- 265, 1987

work page 1987

Show all 20 references

[9]

ACM Trans

Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9:1--9:17 (2008), http://doi.acm.org/10.1145/1435375.1435384

2008
[10]

Couturier, J., Heggernes, P., van 't Hof, P., Kratsch, D.: Minimal dominating sets in graph classes: Combinatorial bounds and enumeration. Theor. Comput. Sci. 487, 82--94 (2013), https://doi.org/10.1016/j.tcs.2013.03.026

2013 doi
[11]

Golovach, Dieter Kratsch, Mathieu Liedloff, and Mohamed Yosri Sayadi

Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, and Mohamed Yosri Sayadi. Enumeration and maximum number of minimal dominating sets for chordal graphs. Theor. Comput. Sci. , 783:41--52, 2019

2019
[12]

Kant \' e , M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Discrete Math. 28(4), 1916--1929 (2014), https://doi.org/10.1137/120862612

2014 doi
[13]

Moon , L

J. Moon , L. Moser , On cliques in graphs. , Israel J. Math 3 (1965) 23--28

1965
[14]

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979

1979
[15]

Brandst\" a dt, V

A. Brandst\" a dt, V. B. Le, J. P. Spinrad, Graph Classes: A Survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999

1999
[16]

Texts in Theoretical Computer Science

Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series, Springer (2010), https://doi.org/10.1007/978-3-642-16533-7

2010 doi
[17]

Golovach, Dieter Kratsch, and Mohamed Yosri Sayadi

Petr A. Golovach, Dieter Kratsch, and Mohamed Yosri Sayadi. Enumeration of maximal irredundant sets for claw-free graphs. Theor. Comput. Sci. , 754:3--15, 2019

2019
[18]

Golovach, Dieter Kratsch, Mathieu Liedloff, and Mohamed Yosri Sayadi

Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, and Mohamed Yosri Sayadi. Enumeration and maximum number of maximal irredundant sets for chordal graphs. Discrete Applied Mathematics , 265:69 -- 85, 2019

2019
[19]

, " * write output.state after.block = add.period write

ENTRY address author booktitle chapter edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.s...
[20]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Below all subsets for minimal connected dominating set

Daniel Lokshtanov, Michal Pilipczuk, and Saket Saurabh. Below all subsets for minimal connected dominating set. SIAM J. Discrete Math. , 32(3):2332--2345, 2018

work page 2018

[2] [2]

P. A. Golovach, P. Heggernes, D. Kratsch, Enumerating minimal connected dominating sets in graphs of bounded chordality , Theor. Comput. Sci. 630 (2016) 63--75

work page 2016

[3] [3]

F. N. Abu-Khzam, A. E. Mouawad, M. Liedloff, An exact algorithm for connected red-blue dominating set, J. of Discrete Algorithms 9 (3) (2011) 252--262

work page 2011

[4] [4]

Skjørten, I.B.: Faster enumeration of minimal connected dominating sets in split graphs (2017)

work page 2017

[5] [5]

Damaschke, P., M \" u ller, H., Kratsch, D.: Domination in convex and chordal bipartite graphs. Inf. Process. Lett. 36(5), 231--236 (1990), https://doi.org/10.1016/0020-0190(90)90147-P

work page doi:10.1016/0020-0190(90)90147-p 1990

[6] [6]

Bang-jensen, J., Huang, J., Macgillivray, G., Yeo, A.: Domination in convex bipartite and convex-round graphs (1999)

work page 1999

[7] [7]

Hedetniemi J

S.T. Hedetniemi J. Pfaff, R. Laskar. NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical Report 428, Department of Mathematical Sciences, Clemenson University , 1983

work page 1983

[8] [8]

The NP-completeness of steiner tree and dominating set for chordal bipartite graphs

Haiko Müller and Andreas Brandstädt. The NP-completeness of steiner tree and dominating set for chordal bipartite graphs. Theoretical Computer Science , 53(2):257 -- 265, 1987

work page 1987