{"id":"880b9761-50ce-4b6e-8fb0-685dfe0275c0","arxiv_id":"2411.18367","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Fair matching is FPT for treewidth plus maximum right-degree, neighborhood diversity, and tree-depth plus number of colors, yet W[1]-hard for feedback vertex number plus tree-depth and for path-width plus number of colors.","lead":"Fair many-to-one matching asks how to assign every applicant on one side to a position on the other side so that each position sees a balanced mix of applicant types. This paper charts when that problem can be solved quickly from the shape of the assignment graph and when it is provably hard.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's reduction is not sound: every vertex v_ab is forced to match all U_{a,b} vertices, none of which has color (b,0), so with L(v_ab)=0 no fair matching exists and the sufficiency construction already fails.","rationale":"The reader's weakest_assumption concerns the tree-depth bound in Theorem 8. I examined that step and believe the path-replacement argument is valid: in a tree-depth forest of G, replacing each V-vertex by a path of |C|+1 vertices preserves ancestor-descendant relations with both its U-neighbors and its V-children, and any root-leaf path containing r V-vertices and s U-vertices has length at most r(|C|+1)+s ≤ (|C|+1)td. The omitted detail is routine, so Theorem 8 is not the main risk. The genuinely load-bearing problem is in Theorem 3, the first W[1]-hardness pillar. There, the set U_{a,b} is defined to contain colors (c,i) for c∈[ℓ]\\{b}, and its vertices have degree exactly one to v_ab. Therefore v_ab is forced to receive at least one vertex of every color except (b,0), while no neighbor of v_ab ever has color (b,0). Since the proof assigns L(v)=0 to v_ab and does not attach a missing-color gadget to it, no L-fair matching can exist at all, regardless of the Multicolored Clique instance. The sufficiency construction is therefore not merely missing a subcase: it describes a matching that violates the fairness constraint at v_ab. This breaks the reduction and leaves the W[1]-hardness claim with respect to (fvn,td) unproved as written. A small repair, such as attaching H[Ĉ_{v_ab}] to each v_ab, might restore the theorem, but the submitted proof is internally inconsistent and needs more than minor clarification. For these reasons I recommend REJECT rather than CONDITIONAL, while acknowledging that other results in the paper, including Theorems 5-8, may remain correct after independent checking.","tokens_in":17495,"tokens_out":20440,"duration_ms":177804,"concrete_test":"Build the smallest instance of the Theorem 3 reduction: let ℓ=2, n=1, and include the single edge between U_1 and U_2. In the matching prescribed by the sufficiency proof, v_12 is matched to the one vertex of color (2,1) from U_{1,2,1} and to the two vertices of U_{1,2} with colors (1,0) and (1,1); no vertex of color (2,0) is matched to v_12, so L(v_12)=0 is violated. Enumerating all left-perfect matchings confirms that the two degree-1 vertices of U_{1,2} force v_12 to have no color-(2,0) neighbor, so every matching is infeasible. If the authors intended a gadget H[Ĉ_{v_ab}] to be attached to v_ab, adding it and re-checking the necessity argument would test that repair; as written, Theorem 3's reduction is invalid.","verdict_should_be":"REJECT","load_bearing_attack":"In Theorem 3, for every a,b with a≠b, all vertices of U_{a,b} are adjacent only to v_ab, so any left-perfect matching must match every vertex of U_{a,b} to v_ab. These U_{a,b} vertices contain exactly one vertex of every color (c,i) with c∈[ℓ]\\{b} and i∈[0,n]. Thus v_ab is always matched to at least one vertex of every color except (b,0). The other neighbors of v_ab are U_{a,b,i}, whose colors are (b,1),...,(b,i), and the edge-gadget sets U^{ab}_{ij}, whose colors are (b,i+1),...,(b,n); none of these supplies color (b,0). The proof explicitly does not attach a gadget H[Ĉ] to v_ab, and it states that L(v)=0 for all non-gadget vertices. Consequently, in the matching described in the sufficiency direction, v_ab has max color count at least 1 and min color count 0, violating L(v_ab)=0. More strongly, because the degree-1 vertices U_{a,b} force v_ab to have matches of all colors c≠b, and no neighbor of v_ab has color (b,0), every left-perfect matching is infeasible. Hence the reduction maps every Multicolored Clique instance to a no-instance, and the claimed W[1]-hardness with respect to (fvn,td) is unsupported as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parameterized complexity of Generalized Fair Matching, a left-perfect many-to-one matching problem with a fairness constraint on the color distribution at each right-hand vertex. The authors propose two W[1]-hardness results, one with respect to the feedback vertex number and tree-depth combined (Theorem 3) and one with respect to path-width, number of colors, and maximum degree of U combined (Theorem 4), as well as FPT results for feedback edge number (Theorem 5), treewidth plus maximum degree of V (Theorem 6), neighborhood diversity (Theorem 7), and tree-depth plus number of colors (Theorem 8). The hardness reductions are from Multicolored Clique and Unary Bin Packing; the FPT algorithms use dynamic programming, a neighborhood-diversity compression, and an ILP solved through a dual tree-depth bound.","tokens_in":17815,"tokens_out":30713,"duration_ms":253346,"significance":"If correct, the results would provide a fairly complete structural classification for a natural fair matching problem and would settle the parameterized status with respect to several important structural parameters. The claimed FPT results, especially the ILP-based tree-depth bound and the Unary Bin Packing reduction, are interesting and potentially valuable. However, the main W[1]-hardness contribution (Theorem 3) is invalid as written, and this undermines the paper's central classification claim. The paper contains no machine-checked proofs or reproducible code; the arguments are standard combinatorial constructions that require careful verification.","major_comments":[{"comment":"The reduction from Multicolored Clique is not sound. In the constructed instance, for every pair a,b with a≠b, each vertex of U_{a,b} has degree exactly 1 and is adjacent only to v_ab. Since the matching is left-perfect, every vertex of U_{a,b} must be matched to v_ab. The set U_{a,b} contains exactly one vertex of every color (c,i) with c∈[ℓ]\\{b} and i∈[0,n], and it contains no vertex of color (b,0). Because v_ab receives no H[Ĉ] gadget, the proof states L(v_ab)=0. Hence in every left-perfect matching, v_ab has at least one matched vertex of every color c≠b and zero matched vertices of color (b,0), so max_c|M_c(v_ab)| - min_c|M_c(v_ab)| ≥ 1 > L(v_ab)=0. Thus every left-perfect matching is infeasible, and the reduction maps every Multicolored Clique instance to a no-instance. In particular, the sufficiency construction in the proof is not L-fair for v_ab, and the claimed W[1]-hardness of Generalized Fair Matching with respect to (fvn, td) is unsupported.","section":"Section 3, Theorem 3"}],"minor_comments":[{"comment":"The definition of the variables x_v and y_v is reversed: the text says they are respectively the maximum and minimum color counts, but the correct intended meaning (as in ILP1 and as required by constraints (8) and (9)) is x_v = min_c |M_c(v)| and y_v = max_c |M_c(v)|. With the printed definition, constraint (9) x_v ≤ count ≤ y_v is contradictory. Please correct the variable definitions.","section":"Section 4, Theorem 8"},{"comment":"The tree-depth bound td(G̃) ≤ (|C|+1)td is asserted as 'clear' without proof. The bound is true: one can replace each V-vertex in an elimination forest of G with a path of |C|+1 vertices and attach each child subtree to the last vertex of the path, yielding an elimination forest of height at most (|C|+1)td. The manuscript should include this argument because the double-exponential runtime of the ILP solver depends on it.","section":"Section 4, Theorem 8"},{"comment":"The statement 'vc ≤ O(2^nd)' is false as written; for example, a complete bipartite graph K_{n,n} has neighborhood diversity 2 and vertex cover number n. The intended implication from FPT with respect to neighborhood diversity to FPT with respect to vertex cover number follows from the reverse inequality nd ≤ 2^{vc}. Please correct the direction and the justification.","section":"Section 5 (Concluding Remark)"},{"comment":"The runtime notation 'O*(22td(|C|+1))' is ambiguous. The proof gives O*((||A||∞+1)^{2^{td_D(A)}}) with td_D(A) ≤ (|C|+1)td, so the theorem should state a double-exponential bound such as O*(2^{2^{(|C|+1)td}}), with clear superscripts.","section":"Section 4, Theorem 8"},{"comment":"In the construction of the sequences (r^1_c,...,r^s_c), the index k is not defined. It should be the largest integer with ∑_{j=1}^k ℓ_j ≤ r_c. Without this definition, the description is incomplete.","section":"Section 4, Theorem 7"}],"recommendation":"reject","confidential_remarks":"The main hardness theorem (Theorem 3) is invalid as written, and the error is not a minor typo: the constructed graph forces every left-perfect matching to violate the fairness constraint at the vertices v_ab. Because the abstract and the introductory claims rest heavily on this result, the paper cannot be accepted in its present form. The other results (Theorems 4-8) appear plausible, and the authors may be able to repair or remove Theorem 3 in a future version, but the current submission does not support its central classification claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The stress-test on Theorem 3 is correct, and it is a load-bearing problem. In the reduction, every vertex in U_{a,b} has degree one and its only neighbor is v_ab. U_{a,b} contains one vertex of every color except (b,0). Since L(v_ab)=0, any left-perfect matching gives v_ab at least n+1 vertices of some colors and zero of color (b,0), so the max-min gap is positive. The sufficiency construction in the proof explicitly matches all of U_{a,b} to v_ab, so it fails on its own terms. The reduction maps every Multicolored Clique instance to a no-instance. This is not a typo-level issue; it invalidates the W[1]-hardness with respect to (fvn, td) as stated.\n\nThe paper does have real value elsewhere. The FPT algorithm for neighborhood diversity genuinely generalizes the earlier |V|-FPT result of Boehmer and Koana, and the dynamic program for treewidth plus ΔV is recognizable and, as far as I checked, correct. The tree-depth plus number of colors result via dual tree-depth of an ILP is an elegant idea, and the claimed bound on the dual graph's tree-depth is plausible through the standard blow-up construction, although the paper only gestures at it. The feedback edge number DP in Theorem 5 also looks sound.\n\nThere are several smaller issues that a revision should clean up. In Theorem 8's ILP2, x_v and y_v are defined as maximum and minimum counts but constraint (9) has them backwards; that is almost certainly a variable-swap typo. In Theorem 7, the removal of K2 components is not correct when |C|=1 and L(v)=0: the component is then feasible, so the blanket claim 'the answer is no' is false. The later rounding of the residue r_c is also under-specified and can produce negative entries; a greedy allocation would fix it. None of these are as serious as the Theorem 3 flaw, but they should be addressed.\n\nMy bottom line: the paper deserves referee time—the topic is current, and the FPT side is a genuine contribution—but the referee should be directed at Theorem 3 first. I would not cite the W[1]-hardness result in its current form, and I would want to see a corrected reduction before recommending acceptance. If the authors can repair Theorem 3 (for instance by attaching a gadget to v_ab that supplies the missing color (b,0), or by changing L(v_ab)), the paper could be a good fit for a parameterized complexity venue.","headline":"Theorem 3's reduction is unsound: forced leaves make every constructed instance infeasible, so the (fvn,td) W[1]-hardness is unsupported; the FPT results look salvageable.","tokens_in":18336,"tokens_out":11372,"would_cite":false,"duration_ms":92486,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Generalized Fair Matching is fixed-parameter tractable for treewidth, neighborhood diversity, and tree-depth plus colors, yet W[1]-hard for feedback vertex number and path-width.","keywords":["fair matching","many-to-one matching","parameterized complexity","W[1]-hardness","fixed-parameter tractable","tree-depth","path-width","neighborhood diversity"],"falsifier":"On small random bipartite graphs, construct ILP2 for a given coloring and compute the tree-depth of its dual graph; any instance where this tree-depth exceeds (|C|+1) times the input graph's tree-depth would refute the bound used in Theorem 8. Alternatively, explicitly search for a counterexample to the claimed subgraph containment of the dual graph in the blown-up graph.","tokens_in":17296,"feed_emoji":"⚖️","tokens_out":10164,"duration_ms":83899,"temperature":0.7,"pith_summary":"Fair many-to-one matching asks for a left-perfect matching in a bipartite graph in which every right-side vertex receives a balanced multiset of colored left-side vertices. The paper establishes a parameterized complexity map for this problem: it is fixed-parameter tractable with respect to neighborhood diversity, to treewidth together with the maximum degree of the right side, and to tree-depth together with the number of colors; it is W[1]-hard with respect to feedback vertex number together with tree-depth even when left-side degrees are at most two, and with respect to path-width together with the number of colors. This matters because such matchings model fair assignment of people or items to resources, and the classification identifies which structural features of the input graph make the problem tractable in principle.","feed_headline":"Fair matching is FPT on treewidth, W[1]-hard on feedback vertices","feed_subtitle":"Tractable for treewidth and neighborhood diversity; W[1]-hard for feedback vertex number and path-width.","key_machinery":"The proof rests on two ILP formulations and on two gadget reductions. ILP1, carrying one pair of variables per vertex of V, generalizes the earlier |V|-parameterized FPT result. ILP2, with one binary variable per edge, has a constraint dual graph that the paper argues is a subgraph of the graph obtained by blowing up each V-vertex into a clique of size |C|+1; the dual-tree-depth ILP theorem then yields the (tree-depth, colors) FPT bound with runtime $O^*(2^{2^{td(|C|+1)}})$. The W[1]-hardness constructions encode Multicolored Clique into graphs of bounded feedback vertex number and tree-depth, and Unary Bin Packing into graphs of bounded path-width, using gadgets that pin the matching to a single choice per color class or per bin.","core_discovery":"The central claim is a dichotomy for the Generalized Fair Matching problem. On the positive side, the paper proves FPT algorithms parameterized by (treewidth, maximum degree of V), by neighborhood diversity (which yields FPT for vertex cover and modular-width), by feedback edge number, and by (tree-depth, number of colors) through an ILP whose dual graph has bounded tree-depth. On the negative side, it proves W[1]-hardness for (feedback vertex number, tree-depth) even with Δ_U=2 via a reduction from Multicolored Clique, and for (path-width, number of colors, Δ_U) via a reduction from Unary Bin Packing. Together these results draw the algorithmic boundary of the problem in terms of structural graph parameters.","pith_inferences":["The tree-depth bound for the ILP dual graph in Theorem 8 is the most delicate step; if the asserted containment fails for some instance, the theorem would need a different structural argument to survive.","The hardness reductions use thresholds 0 and 1 on right-side vertices, so an FPT result for the uniform-threshold Fair Matching problem would not follow from these constructions.","Given the W[1]-hardness for (feedback vertex number, tree-depth), the open question of FPT for (feedback vertex number, number of colors) looks unlikely to have a positive answer.","The neighborhood-diversity FPT result suggests that a polynomial kernel for vertex cover may exist, which would strengthen the tractability picture."],"forward_implications":["A correct FPT algorithm for (treewidth, Δ_V) means the problem is solvable in polynomial time on graphs of bounded treewidth whenever right-side degrees are bounded.","The neighborhood-diversity FPT result subsumes the earlier FPT bound in terms of |V| and transfers to vertex cover and modular-width parameters.","The (tree-depth, colors) result gives a double-exponential runtime that is nevertheless fixed-parameter tractable, so instances with small tree-depth and few colors are algorithmically accessible.","The W[1]-hardness for (feedback vertex number, tree-depth) rules out FPT algorithms for either parameter alone under standard complexity assumptions.","The path-width hardness shows that replacing tree-depth by path-width in the positive result is impossible, even when the number of colors and left-side degrees are bounded."],"supporting_citations":[{"why":"Defines Fair Matching, proves NP-hardness and FPT with respect to |V| via ILP1; the present paper extends and builds on these results.","marker":"[4]"},{"why":"Supplies the ILP theorem that solving an integer program is FPT with respect to the dual tree-depth of the coefficient matrix, used in Theorem 8.","marker":"[9]"},{"why":"Proves Multicolored Clique is W[1]-hard, the source problem for the first W[1]-hardness reduction.","marker":"[10]"},{"why":"Proves Unary Bin Packing is W[1]-hard with respect to the number of bins, the source problem for the second W[1]-hardness reduction.","marker":"[14]"},{"why":"Provides Lenstra's fixed-variable ILP algorithm used to obtain FPT time for ILP1 and Theorem 1.","marker":"[21]"}],"fun_headline_variants":["Fair matching: FPT on treewidth and neighborhood diversity","Fair matching: W[1]-hard even when feedback vertex set and tree-depth are small","Fair matching: FPT on treewidth, W[1]-hard for small feedback vertex set and tree-depth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The FPT result for tree-depth combined with the number of colors relies on the unproved structural claim that the integer program's dual constraint graph has tree-depth at most (|C|+1) times the tree-depth of the input graph; if that bound fails, the double-exponential runtime guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["Fair matching: FPT on treewidth and neighborhood diversity","Fair matching: W[1]-hard even when feedback vertex set and tree-depth are small","Fair matching: FPT on treewidth, W[1]-hard for small feedback vertex set and tree-depth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.003714,"raw_usage":{"total_tokens":13921,"prompt_tokens":938,"completion_tokens":12983,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":12912}},"tokens_in":554,"tokens_out":12983,"duration_ms":87601,"temperature":1.0,"reasoning_tokens":12912,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:19:28.695112+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On small random bipartite graphs, construct ILP2 for a given coloring and compute the tree-depth of its dual graph; any instance where this tree-depth exceeds (|C|+1) times the input graph's tree-depth would refute the bound used in Theorem 8. Alternatively, explicitly search for a counterexample to the claimed subgraph containment of the dual graph in the blown-up graph.","supporting_citations":[{"cited_title":"The complexity of finding fair many-to-one matchings","cited_arxiv_id":null,"evidence_quote":"Defines Fair Matching, proves NP-hardness and FPT with respect to |V| via ILP1; the present paper extends and builds on these results."},{"cited_title":"On the parameterized complexity of multiple-interval graph problems","cited_arxiv_id":null,"evidence_quote":"Proves Multicolored Clique is W[1]-hard, the source problem for the first W[1]-hardness reduction."},{"cited_title":"Bin packing with fixed number of bins revisited","cited_arxiv_id":null,"evidence_quote":"Proves Unary Bin Packing is W[1]-hard with respect to the number of bins, the source problem for the second W[1]-hardness reduction."}],"review_version":1}