pith. sign in

arxiv: 1906.10801 · v1 · pith:7ONC2UJ5new · submitted 2019-06-26 · 💻 cs.DS

Upper and Lower Bounds on Approximating Weighted Mixed Domination

Mingyu Xiao This is my paper

Pith reviewed 2026-05-25 15:36 UTC · model grok-4.3

classification 💻 cs.DS
keywords mixed dominating setapproximation algorithmsinapproximabilityweighted graphsNP-hardnessUnique Games Conjecturedomination problems
0
0 comments X

The pith

Weighted mixed domination has a 2-approximation when edge weights are at least vertex weights but resists better approximations otherwise.

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

The paper studies the approximability of finding a minimum-weight mixed dominating set, where a mixed set of vertices and edges must cover all vertices and edges in the graph. It gives a 2-approximation algorithm that applies whenever every edge has weight at least as large as every vertex. For three other ranges of the edge-to-vertex weight ratio the paper proves matching-style inapproximability thresholds under the assumptions P ≠ NP and the Unique Games Conjecture. The results therefore partition the problem into one polynomially approximable regime and three regimes whose best possible approximation ratios are bounded away from 1.

Core claim

For the weighted mixed domination problem with uniform vertex weight w_v and edge weight w_e, a 2-approximation algorithm exists whenever w_e ≥ w_v. The problem cannot be approximated within 1.3606 unless P=NP (or within 2 under UGC) when w_e ≥ 2w_v; cannot be approximated within 1.1803 unless P=NP (or within 1.5 under UGC) when 2w_v > w_e ≥ w_v; and cannot be approximated within (1−ε)ln|V| unless P=NP when w_e < w_v.

What carries the argument

Case distinction on the ratio w_e/w_v together with a 2-approximation algorithm for the regime w_e ≥ w_v and hardness reductions from vertex cover or set cover for the remaining regimes.

If this is right

  • Any instance with w_e ≥ w_v can be solved to within a factor of 2 in polynomial time.
  • No algorithm can improve the constant-factor guarantee below 1.3606 for sufficiently heavy edges unless P=NP.
  • The logarithmic hardness when vertices are heavier shows the problem is at least as hard as set cover.
  • The intermediate ratio interval 2w_v > w_e ≥ w_v has its own distinct constant hardness threshold of 1.1803.

Where Pith is reading between the lines

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

  • The weight ratio acts as a phase-transition parameter that decides whether the optimum prefers edges or vertices.
  • It is natural to ask whether approximation algorithms exist that match the hardness thresholds exactly in each regime.
  • The same weight-ratio case analysis may extend to other mixed selection problems on graphs.

Load-bearing premise

All inapproximability statements rest on the assumptions that P is not equal to NP and that the Unique Games Conjecture is true.

What would settle it

A polynomial-time algorithm achieving an approximation ratio strictly better than 1.3606 on instances with w_e ≥ 2w_v would falsify the corresponding inapproximability claim (assuming P ≠ NP).

Figures

Figures reproduced from arXiv: 1906.10801 by Mingyu Xiao.

Figure 1
Figure 1. Figure 1: An illustration of the construction of G3 to all vertices in G0 i , where G0 i contains a copy of G, an induced matching Mi with size |Mi | = i, and a complete bipartite graph between the vertices of G and the left part of the induced matching Mi . This is to say, Vi = V ∪ {aj} i j=1∪ {bj} i j=1∪ {cj} 2n j=0 and Ei = E ∪Mi∪Hi∪Fi , where Mi = {aj bj} i j=1, Hi = {vaj |v ∈ V, j ∈ {1, . . . , i}}, and Fi = {c… view at source ↗
read the original abstract

A mixed dominating set of a graph $G = (V, E)$ is a mixed set $D$ of vertices and edges, such that for every edge or vertex, if it is not in $D$, then it is adjacent or incident to at least one vertex or edge in $D$. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is $NP$-hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight $w_v$ and all edges are assigned the same nonnegative weight $w_e$, and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: [1.] for $w_e\geq w_v$, a 2-approximation algorithm; [2.] for $w_e\geq 2w_v$, inapproximability within ratio 1.3606 unless $P=NP$ and within ratio 2 under UGC; [3.] for $2w_v > w_e\geq w_v$, inapproximability within ratio 1.1803 unless $P=NP$ and within ratio 1.5 under UGC; [4.] for $w_e< w_v$, inapproximability within ratio $(1-\epsilon)\ln |V|$ unless $P=NP$ for any $\epsilon >0$.

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.

Referee Report

2 major / 3 minor

Summary. The paper studies the weighted mixed dominating set problem, where a mixed set D of vertices and edges must dominate all vertices and edges, minimizing the total weight with uniform vertex weight w_v and edge weight w_e. It partitions the problem into four regimes based on the ratio w_e/w_v and claims: a 2-approximation algorithm when w_e ≥ w_v; inapproximability within 1.3606 (unless P=NP) and 2 (under UGC) when w_e ≥ 2w_v; inapproximability within 1.1803 (unless P=NP) and 1.5 (under UGC) when 2w_v > w_e ≥ w_v; and inapproximability within (1-ε)ln|V| (unless P=NP) when w_e < w_v.

Significance. If the claims hold, the results give a tight characterization of approximability for weighted mixed domination across all weight ratios, extending the known 2-approximation for the unweighted case and providing the first detailed hardness landscape for the weighted variant. The matching upper and lower bounds in each regime strengthen the contribution.

major comments (2)
  1. [§3] §3 (Algorithm): The 2-approximation for w_e ≥ w_v is stated to build on the unweighted case, but the manuscript does not explicitly verify that the greedy selection of minimum-weight elements preserves the factor when w_e = w_v exactly; a short case analysis or charging argument would confirm this does not degrade.
  2. [§4.2] §4.2 (Hardness for w_e ≥ 2w_v): The reduction establishing 1.3606-inapproximability appears to adapt the standard vertex cover reduction, but the weight scaling step that enforces the 2w_v threshold is only sketched; the manuscript should include the explicit gadget weights to allow verification that no cheaper mixed set is created.
minor comments (3)
  1. [§2] The notation for mixed sets (vertices and edges) is introduced in the abstract but the formal definition in §2 uses D ⊆ V ∪ E without clarifying incidence vs. adjacency for edges; a single sentence would improve readability.
  2. [Table 1] Table 1 summarizing the four regimes would benefit from an extra column listing the matching upper/lower bounds side-by-side for quick reference.
  3. [§1.2] A few citations to prior mixed-domination papers (e.g., the unweighted 2-approx) are present but the related-work section could explicitly contrast the new weighted hardness thresholds with existing results on weighted domination.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and helpful suggestions. We address the two major comments below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (Algorithm): The 2-approximation for w_e ≥ w_v is stated to build on the unweighted case, but the manuscript does not explicitly verify that the greedy selection of minimum-weight elements preserves the factor when w_e = w_v exactly; a short case analysis or charging argument would confirm this does not degrade.

    Authors: We agree that an explicit verification at the boundary w_e = w_v strengthens the presentation. In the revision we will insert a short case analysis (approximately one paragraph) that applies the same charging argument used for the unweighted case, confirming that equal weights do not degrade the 2-approximation guarantee. revision: yes

  2. Referee: [§4.2] §4.2 (Hardness for w_e ≥ 2w_v): The reduction establishing 1.3606-inapproximability appears to adapt the standard vertex cover reduction, but the weight scaling step that enforces the 2w_v threshold is only sketched; the manuscript should include the explicit gadget weights to allow verification that no cheaper mixed set is created.

    Authors: We accept that the weight-scaling details are only sketched. The revised §4.2 will list the concrete gadget weights (vertex weight w_v, edge weight 2w_v, and auxiliary edges) together with a short paragraph verifying that any mixed dominating set cheaper than the intended threshold would imply a vertex cover smaller than the known inapproximability bound. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a 2-approximation algorithm for the case w_e ≥ w_v and establishes inapproximability results via standard reductions from known NP-hard problems under the external assumptions P ≠ NP and UGC. These results rely on conventional complexity-theoretic techniques and do not reduce any claimed prediction or bound to a quantity defined in terms of itself within the paper. The weight-ratio case distinctions follow directly from the problem definition and are not self-referential. No self-citation is load-bearing for the central claims, and the derivation chain remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on two standard complexity assumptions for its hardness results; no free parameters or invented entities appear in the abstract.

axioms (2)
  • standard math P ≠ NP
    Invoked to establish inapproximability unless P=NP for all four weight cases.
  • domain assumption Unique Games Conjecture
    Invoked to obtain the stronger inapproximability ratios under UGC.

pith-pipeline@v0.9.0 · 5835 in / 1202 out tokens · 46301 ms · 2026-05-25T15:36:19.761340+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Abu-Khzam, M.R

    F.N. Abu-Khzam, M.R. Fellows, M.A. Langston, W.H. Suters: Crown structures for vertex cover kernelization. Theory Comput. Syst. , 41 (3):411–430 (2007)

    work page 2007

  2. [2]

    Alavi, M

    Y. Alavi, M. Behzad, L. M. Lesniak-Foster, and E. A. Nordhaus. Total matchings and total coverings of graphs. Journal of Graph Theory , 1(2):135–140 (1977)

    work page 1977

  3. [3]

    Alavi, J

    Y. Alavi, J. Liu, J. Wang, and Z. Zhang. On total covers of graphs. Discrete Mathe- matics, 100(1-3):229–233 (1992)

    work page 1992

  4. [4]

    Dinur and M

    I. Dinur and M. Safra. The importance of being biased. In Proc. STOC’02, pages 33–42, 2002

    work page 2002

  5. [5]

    Dinur and D

    I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Proceedings of the 46th annual ACM symposium on Theory of computing , pages 624–633, 2014

    work page 2014

  6. [6]

    Escoffier, J

    B. Escoffier, J. Monnot, V. Th. Paschos and M. Xiao. New Results on Polynomial In- approximabilityand Fixed Parameter Approximability of Edge Dominating Set. Theory Comput. Syst. , 56(2): 330–346 (2015)

    work page 2015

  7. [7]

    Fujito and H

    T. Fujito and H. Nagamochi. A 2-approximation algorithm for the minimum weight edge dominating set problem. Disc. Appl. Math. , 118(3):199–207 (2002)

    work page 2002

  8. [8]

    M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman and company, 1979

    work page 1979

  9. [9]

    P. Hatami. An approximation algorithm for the total covering problem. Discussiones Mathematicae Graph Theory , 27(3):553–558 (2007)

    work page 2007

  10. [10]

    T. W. Haynes, S. Hedetniemi and P. Slater. Fundamentals of Domination in Graphs. CRC Press, Boca Raton, 1998

    work page 1998

  11. [11]

    S. T. Hedetniemi and R. C. Laskar. Bibliography on domination in graphs and some basic definitions of domination parameters. Discrete Mathematics, 86(1):257–277 (1991)

    work page 1991

  12. [12]

    P. Jain, M. Jayakrishnan, F. Panolan and A. Sahu. Mixed Dominating Set: A Parame- terized Perspective. In WG, LNCS 10520, pages 330–343, 2017

    work page 2017

  13. [13]

    D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci. , 9(3):256–278, (1973)

    work page 1973

  14. [14]

    Khot and O

    S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2 − ε. J. Comput. System Sci. , 74(3):335–349 (2008)

    work page 2008

  15. [15]

    J. K. Lan and G. J. Chang. On the mixed domination problem in graphs . Theoretical Computer Science, 476: 84–93 (2013)

    work page 2013

  16. [16]

    D. F. Manlove. On the algorithmic complexity of twelve covering and independence parameters of graphs. Discrete Applied Mathematics , 91(1-3):155–175 (1999)

    work page 1999

  17. [17]

    G. L. Nemhauser and L. E. Trotter. Properties of vertex packing and independence system polyhedra. Mathematical Programming, 6(1):48–61 (1974)

    work page 1974

  18. [18]

    Nieberg and J

    T. Nieberg and J. Hurink. A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs. In WAOA, LNCS 3879, pages 296–306, 2005

    work page 2005

  19. [19]

    Raz and S

    R. Raz and S. Safra. A sub-constant error-probability low-degree test, and a sub- constant error-probability PCP characterization of NP. In Twenty-Ninth ACM Sympo- sium on Theory of Computing , pages 475–484, 1997

    work page 1997

  20. [20]

    M. Xiao, T. Kloks, and S. H. Poon. New parameterized algorithms for edge dominating set. Theoretical Computer Science , 511:147–158 (2013) Upper and Lower Bounds on Approximating Weighted Mixed Domination 17

    work page 2013

  21. [21]

    Xiao and H

    M. Xiao and H. Nagamochi. Parameterized edge dominating set in graphs with degree bounded by 3. Theoretical Computer Science , 508:2–15 (2013)

    work page 2013

  22. [22]

    Yannakakis and F

    M. Yannakakis and F. Gavril. Edge dominating sets in graphs. SIAM Journal on Applied Mathematics, 38(3):364–372 (1980)

    work page 1980

  23. [23]

    Y. Zhao, L. Kang, and M. Y. Sohn. The algorithmic complexity of mixed domination in graphs. Theoretical Computer Science , 412(22):2387–2392 (2011)

    work page 2011