REVIEW 3 major objections 6 minor 21 references
Pairwise similarity method for majority domination problem
T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proposes guaranteed-error heuristics for the NP-hard majority domination number, with its core bound for a spanning tree $T$ of a connected graph $G$ being $\gamma(T)-4k \le \gamma(G) \le \gamma(T)+2l$.
desk verdict Refined bounds are real, but the guaranteed-accuracy claim for the heuristics does not follow from the theorems — the key quantity l uses optimal functions of intermediate graphs the algorithm never has. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key machinery is the pairwise similarity function, a distance-like comparison between instances that is not required to satisfy metric axioms. For this problem the distance is the minimum number of edge deletions or additions needed to reach the special case, and the cost of that distance is controlled by Lemmas 2 and 3, which bound the change in $\gamma$ per edited edge with constants $-4$, $-2$, $0$, and $+2$ depending on whether the endpoints are 'for-for', 'against-against', or mixed in the optimal opinion function. Theorems 1–3 then add these edge contributions along a sequence of graphs connecting the original instance to the special case. The repair operator—check strict majority after each edit, and if it fails, change an incident opinion from $-1$ to $+1$—is what makes the special-case solution feasible for the original graph.
What would settle it
Run the spanning-tree heuristic on every connected graph with up to seven vertices, compute the true $\gamma(G)$ by exhaustive search, and compare the returned opinion sum with the interval $\gamma(T)-4k \le \gamma(G) \le \gamma(T)+2l$ using $l$ counted from the edge-endpoint opinions that the repair path actually encounters; a single graph whose returned sum lies outside that interval, or whose repair needs more than $l$ flips, would refute the guaranteed-accuracy claim.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that the NP-hard majority domination number can be approximated with a guaranteed absolute error by viewing every graph as an edited copy of a polynomial special case. The engine is a one-edge stability bound: deleting or adding a single edge moves $\gamma$ by at most $-4$ or $+2$, and Lemmas 2 and 3 refine this by endpoint-opinion cases, so that an edge between two 'for'-voting endpoints can be added without increasing the upper bound at all. Summing these bounds over the $k$ edges that separate $G$ from a spanning tree $T$ gives the interval $\gamma(T)-4k \le \gamma(G) \le \gamma(T)+2l$, and the same summation logic applied to completions and regularizations produces comparable intervals in the complete-graph and regular-graph cases. Each interval is interpreted as a pairwise similarity function: a certified distance from the original instance to the nearest easy case. The accompanying repair step—flip an incident $-1$ to $+1$ whenever an edge edit breaks strict majority—converts the easy-case solution into a feasible opinion function for $G$, and the similarity function then serves as a post-processing criterion for choosing among heuristics.
Load-bearing premise
The accuracy guarantee depends on classifying every deleted edge by the 'for'/'against' opinions of its endpoints in the optimal voting configurations of the intermediate graphs, while the repair algorithm only ever knows its own non-optimal opinion function; if those two labelings disagree, the promised interval stops controlling the algorithm's actual output.
Editorial extensions
If this is right
- Theorem 1 brackets the majority domination number of any connected graph $G$ by the polynomial-time computable value $\gamma(T)$ plus simple edge counts: $\gamma(T)-4k \le \gamma(G) \le \gamma(T)+2l$, so no hard search is needed to get an approximation whose error grows linearly in the cyclomatic number.
- The complete-graph route gives an $O(|V|+|E|)$ heuristic whose error is governed by Theorem 2: each deleted edge contributes at most $+2$ to the upper bound, while the lower-side penalty depends on whether the deleted edges are incident to 'for' vertices, 'against' vertices, or mixed pairs.
- For odd-order graphs, the regular-graph route combines an analytic formula for $\gamma$ on $k$-regular graphs with edit distance, and Theorem 3 bounds the total effect of the $l$ removed and $m$ added edges by $-4l-2m$ on the low side and $+2l+4m$ on the high side.
- The three pairwise similarity functions give a post-processing selection rule: before running any repair, estimate the guaranteed interval for each special case and keep the heuristic whose promised error is smallest.
Reading between the lines
- The same edge-counting recipe should transfer to any NP-hard optimization problem whose objective changes by a fixed constant under a single element-deletion or element-addition; any exactly solvable subclass would then automatically supply a certified heuristic.
- Since the upper bound in Theorem 1 depends only on $l$, the number of deleted edges whose endpoints are not both 'for', a testable improvement is to choose the spanning tree that minimizes $l$ under the repair path actually used; the paper states that its refined lemmas are meant to enable spanning-tree selection but does not implement it.
- The regular-graph branch is explicitly left open on two practical points—which edit-distance heuristic to use and which target degree to select—so the guarantee of Theorem 3 is certified only for the regular graph the algorithm happens to produce; an empirical comparison of mean versus median target degree and greedy versus exact edit distance on random graphs would quantify the remaining slack.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the majority domination number gamma(G), the minimum total opinion f(V) over {−1,+1} vertex labelings such that a strict majority of vertices vote 'for' under a two-tier majority rule. The authors propose a 'pairwise similarity method' to approximate gamma(G) by solving three special graph classes: trees, complete graphs, and regular graphs with an odd number of vertices. The main theoretical results are Theorems 1–3, which bound gamma(G) in terms of gamma(T) for a spanning tree T and in terms of gamma(H) for a complete or regular graph H, with correction terms involving the number and types of added or deleted edges. The paper then presents repair algorithms that start from an optimal solution for the special case and flip −1 vertices to +1 as edges are added or deleted, claiming these heuristics have guaranteed accuracy and can be selected in a post-processing step.
Significance. The pairwise-similarity framework is conceptually interesting, and the paper is transparent about open questions, particularly in the regular-graph case. The bounds in Theorems 2 and 3 are derived from previously published lemmas and do not involve fitted parameters, and the paper does not engage in circular reasoning. However, the central advertised claim—that the proposed heuristics have guaranteed accuracy—is not established. The theorems bound the true optimal values of the graphs involved, but the algorithms' repair steps are governed by the optimal solution of the starting special case and by the algorithm's own feasible functions, not by the optimal functions of the intermediate graphs. As a result, the parameters l, s, and m in the bounds do not control the algorithms' actual outputs. The paper also provides no experimental evaluation. If the information gap could be closed, the approach would yield O(k)-approximations in polynomial time for the tree-based case, which would be a genuine contribution; as written, the main claim fails.
major comments (3)
- [Theorem 1 and Section 3 algorithm] The upper bound in Eq. (3.9), gamma(G) <= gamma(T)+2l, is stated with l defined as the number of non-'pro-pro' edges among the k removed edges, but the proof applies Lemma 3 sequentially and therefore requires l to be computed with respect to the optimal opinion functions of the intermediate graphs H_i. The repair algorithm in Section 3 knows only the optimal function of the tree T and its own successive repairs; it does not know the optimal functions of the H_i. Its flip count q is not shown to satisfy q <= l. If an intermediate graph H_{i-1} has an optimal solution with fewer +1 vertices than the algorithm's current function f, an edge that is 'pro-pro' in that optimal solution can still be incident to a -1 vertex under f, causing the algorithm to flip and q to exceed l. Consequently, the output value gamma(T)+2q can exceed gamma(T)+2l, and the advertised refined accuracy guarantee for the algorithm does not follow. The coarse bound q <= k would still give an O(k) error, but the refined 2l bound and the post-processing selection criterion based on it are unsupported.
- [Theorem 2 and Section 4 algorithm] Theorem 2 (Eq. (4.2)) bounds gamma(G)-gamma(H) in terms of l, s, and m, which are defined via edge classifications relative to the optimal opinion functions of the graphs in the deletion sequence, since Lemma 2 applies to the graph before each deletion. The algorithm in Section 4 constructs a majority function for the complete graph and then deletes edges, flipping an incident -1 vertex to +1 whenever the majority condition fails. At each deletion step, the current function need not be optimal for the current graph, so the parameters l, s, and m of Theorem 2 are not the parameters of the algorithm's actual flips. The claim that inequality (4.2) provides an accuracy estimate for the constructed solution is therefore not justified; it bounds only the optimal-value difference, not the difference between gamma(G) and the algorithm's output.
- [Section 5, regular graph heuristic] The regular-graph heuristic's guaranteed accuracy is not established. Theorem 3 (Eq. (5.1)) bounds gamma(G)-gamma(H) in terms of the exact numbers l and m of deleted and added edges between G and a regular graph H. The algorithm, however, finds H via a greedy degree-matching heuristic for the edit distance, which has no proven approximation guarantee. If the greedy heuristic returns a regular graph at edit distance d' > d = l+m, the bound of Theorem 3 does not apply to the actual solution. The paper explicitly leaves the edit-distance problem open (Section 5), so the 'guaranteed accuracy' claim for this case is not supported.
minor comments (6)
- [Section 3, algorithm step 2] The rule 'Determine an incident vertex of the new edge with opinion −1' is ambiguous when both endpoints have opinion −1; the paper should specify which endpoint is flipped and prove that one flip suffices in all cases.
- [Lemma 2, proof, case f(u)=f(v)=-1] In the first part of the proof, the statement that after flipping one vertex its neighbor sum 'remains the same' is inaccurate; the sum increases by 1 for both endpoints. The argument's conclusion is still correct, but the explanation should be corrected.
- [Section 5, Eq. (5.2)] The formula for gamma(n,k) is presented as a known result but without an explicit derivation or reference at the point of use; please cite Chebotarev and Peleg (2023) directly in the statement or add a brief explanation.
- [Title and general text] The English title 'Pair wise' should be 'Pairwise', and there are numerous typographical and grammatical errors throughout the English text that should be corrected.
- [Figure 1] Figure 1 is referenced in Section 5 but appears only at the end of the manuscript; consider placing it closer to its first mention and ensure the caption clearly describes the original graph G and the 4-regular graph H.
- [Abstract and Section 6] The abstract and conclusion claim criteria for selecting the optimal algorithm during post-processing, but no concrete selection procedure is described; the paper only provides bounds that could in principle guide selection, so the claim overstates what is actually delivered.
Circularity Check
No significant circularity: accuracy bounds are derived from the definition of gamma(G) via new lemmas, and reference [6] is not load-bearing.
full rationale
The paper's main results (Lemmas 2-3, Theorems 1-3) are proved from the definition of strict majority domination gamma(G) and elementary observations about how adding/removing an edge affects vertices' voting conditions. Theorem 1's bound (3.9) is a genuine inequality relating gamma(T) to gamma(G), obtained by summing Lemma 3 inequalities over the sequence of added edges; it is not an identity that defines gamma(G). The quantities s and l are defined in terms of optimal opinion functions of intermediate graphs, and the paper does not show that the repair algorithm's flip count equals l; this is a correctness gap in the claimed guaranteed accuracy, not a circular reduction of the result to its input. Similarly, Theorem 2 and Theorem 3 are summations of Lemma 1/Lemma 2 bounds and do not presuppose the theorem being proved. Reference [6], authored in part by the current authors, supplies the pairwise-similarity framework and an earlier Lemma 1, but the present paper's central theorems are proved here, and Lemma 1 is a simple, parameter-free statement not containing the target results. No fitted parameter is renamed as a prediction, no uniqueness claim is imported, and no ansatz is smuggled in by citation. The derivation chain is therefore self-contained; any deficiency lies in proof of applicability to the algorithm's output, not in circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption Lemma 1 from prior work [6]: for any graph G and H=G minus one edge, -4 <= gamma(G)-gamma(H) <= 2.
- domain assumption Analytic values gamma(n,k) for connected regular graphs with odd n, taken from [2], are correct and applicable.
- ad hoc to paper The edit distance to the nearest regular graph can be found or well-approximated by the proposed greedy degree-matching heuristic.
Cite this review
Pith. "Pith review of Pairwise similarity method for majority domination problem." pith.science (2026). https://pith.science/paper/7U6B4YBV
@misc{pith2026250608886,
author = {Pith},
title = {Pith review of: Pairwise similarity method for majority domination problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/7U6B4YBV}},
note = {Machine review of arXiv:2506.08886}
}
read the original abstract
The paper considers the problem of finding the number of dominant voters in two-level voting procedures. At the first stage, voting is conducted among local groups of voters, and at the second stage, the results are aggregated to form a final decision. The goal is to determine the minimum proportion of voters supporting a proposal for it to be accepted. The paper uses the method of pairwise comparisons to analyze the structure of the problem and develop heuristic algorithms with guaranteed accuracy. Special cases are considered, including the agent communication graph as a tree, complete graph, or regular graph with an odd number of vertices. New heuristic algorithms are proposed for each case, along with pairwise comparison functions to estimate the accuracy of the solution. Results extend the use of polynomial algorithms to a broader class of problems, providing criteria for selecting the optimal algorithm during the post-processing stage.
Reference graph
Works this paper leans on
-
[1]
Вершинаv∈Vимеет множество сосе- дейN v ={w∈V: (v, w)∈E}, в которое входит иv
Постановка задачи.Рассматривается графG= (V, E),|V|=n, каждая вершина которого имеет петлю. Вершинаv∈Vимеет множество сосе- дейN v ={w∈V: (v, w)∈E}, в которое входит иv. На множестве вершинV задается функция мненийf:V→ {−1,1}, которая каждой вершине ставит в соответствие ее мнение. Функция мнений расширяется на подмножестваW⊆V как сумма мнений вершин множ...
-
[2]
Метод попарного сходства.В данной работе предлагается исполь- зовать метод попарного сходства для расширения применения алгоритмов для простых специальных случаев и с помощью функции попарного сходства ана- лизировать успешность такого расширения. Методпопарногосходстваобобщаетметрическийподход,которыйизначаль- но был сформулирован для задач теории распис...
-
[3]
Найти один или несколько специальных случаев задачи
-
[4]
Построить функцию попарного сходства, которая позволяет оценивать расстояние от любой задачи до каждого из возможных специальных слу- чаев
-
[5]
Найти ближайший специальный случай к заданному примеруA, исполь- зуя выбранную функцию попарного сходства
-
[6]
Найти решение наиболее близкого примера кAиз множества примеров, которые являются специальным случаем
-
[7]
Оценить гарантированную погрешность полученного решения с помощью соответствующей функции попарного сходства
-
[8]
Проверить полученное решение на допустимость, и если какие-то ограни- чения нарушены, то использовать функцию, преобразующуюXB вX A = X ∗ B. Рекомендации, по нахождению новых специальных случаев, а также алго- ритм для нахождения функции попарного сходства можно найти в [6]. 5 После построения функции попарного сходства предлагается синтезировать алгоритм...
Show all 21 references
-
[9]
Специальный случай на основе графа дерева.В работе [6] пред- ставлен алгоритм для решения задачи поиска числа строгого доминирования. Он заключается в переходе от исходной задачи к её специальному случаю — за- дачесграфоммненийввидеостовногодереваисходногографа.Затемалгоритм в...
-
[10]
Вычислить оптимальную строго ма- жоритарную функцию мнений для остовного дерева с помощью полино- миального алгоритма
Найти остовное деревоTграфаG. Вычислить оптимальную строго ма- жоритарную функцию мнений для остовного дерева с помощью полино- миального алгоритма
-
[11]
Проверить вы- полнимость|V +|>|V|/2для текущей функции мнений
Последовательно добавитьkребер к остовному деревуTдо достижения графаG: Добавить ребро, которое принадлежитE(G)∖E(T). Проверить вы- полнимость|V +|>|V|/2для текущей функции мнений. Если нера- венство выполняется, перейти к добавлению следующего ребра. Определить инцидентную к ...
-
[12]
Специальный случай на основе полного графа.Рассмотримспе- циальный случай задачи нахождения числа доминирования с графом связей в виде полного графа. В этом случае минимальное число доминирования равно двум в случае четного количества вершин и 1 в случае нечетного количества: ...
-
[13]
Построить мажоритарную функций мнений вершин с(n−1)//2количеством вершин с мнением «против»
Достроить графGдо полногоK. Построить мажоритарную функций мнений вершин с(n−1)//2количеством вершин с мнением «против». В первую очередь определить мнения «против» вершин из множества вер- шин которые смежны достраиваемым ребрам
-
[14]
Проверить вы- полнимость|V +|>|V|/2для текущей функции мнений
Последовательно удалитьkребер до достижения графаG: Удалить ребро, которое принадлежитE(K)∖E(G). Проверить вы- полнимость|V +|>|V|/2для текущей функции мнений. Если нера- венство выполняется, перейти к удалению следующего ребра. Определить инцидентную к удаленному ребру вершин...
-
[15]
Для перехода от исходного графа к регулярному необходимо удалять и до- бавлять ребра
Специальный случай на основе регулярного графа.Рассмот- рим специальный случай связного регулярного графа с нечетным количеством вершин [2]. Для перехода от исходного графа к регулярному необходимо удалять и до- бавлять ребра. На основе леммы 1 сформулируем оценку отклонения ч...
-
[16]
Определим степени вершин исходного графа
-
[17]
Степень должна быть четной, так как сумма всех сте- пеней в регулярном графе равнаяnkдолжна быть чётной
Выберем степень регулярностиk, равную ближайшему целому среднему 1 исходного графа. Степень должна быть четной, так как сумма всех сте- пеней в регулярном графе равнаяnkдолжна быть чётной
-
[18]
Генерируемk−регулярный граф с тем же количеством вершин
-
[19]
Сравниваем графы по редактирующему расстояниюdи выбираем с наи- меньшим значением. На рис. 1 представлен результат работы алгоритма. Для графаGнайден ближайший4-регулярный графHс редактирующим расстоянием3. Сложность представленного алгоритма за исключением поиска редактирующе...
-
[20]
В дан- ной работе продемонстрировано использование метода попарного сходства для задачи поиска числа доминирования в результате которого обе цели были вы- полнены
Заключение.Основной целью применения метода попарного сход- ства является исследование структурN P−полных задач и расширение приме- нимости полиномиальных алгоритмов на более широком классе задач. В дан- ной работе продемонстрировано использование метода попарного сходства для...
2017
-
[55]
№. 10. P. 2875-2880. 19 Подписи к рисункам статьи Шушко и др., ТиСУ 2025, № Рис. 1. Исходный графGи4-регулярный графH, с редактирующим рас- стоянием3. 20 G H Рис. 1. Шушко и др., ТиСУ 2025, № 21
2025
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.