{"id":"7e506b4b-1ea7-46ea-b640-9e7081d9c671","arxiv_id":"1908.08882","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Simultaneous proper interval graphs can be recognized in linear time and simultaneous unit interval graphs in O(|V||E|) time in the sunflower case, and both become NP-complete without the sunflower restriction.","lead":"In this paper, the authors give fast recognition algorithms for simultaneous proper interval graphs (linear time) and simultaneous unit interval graphs (O(|V||E|) time) in the sunflower case, where all input graphs share one common subgraph. They also show that both problems become NP-complete when the number of input graphs is unrestricted and the sunflower structure is dropped.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 8's characterization of simultaneous enumerations is false as stated: a 'reversible part' may reverse a component that spans two blocks of the shared graph, changing the shared-block order and yielding a non-simultaneous enumeration.","rationale":"The reader correctly identified the unit-interval recognition proof as the least secure part, but located the risk in Theorem 13's scouting/zipping lemmas. My independent scrutiny found a different, more concrete failure: Theorem 8, which the same algorithm uses to restrict the search to simultaneous enumerations obtained by reversals, is false as stated. The counterexample above is small, uses only two graphs, satisfies the connectedness and sunflower assumptions, and directly violates the 'if' direction of Theorem 8. Since Theorem 17's correctness proof depends on Theorem 8, the central claim that simultaneous unit interval graphs can be recognized in O(|V||E|) time is not established by the manuscript as written. The proper-interval recognition algorithm (Theorem 6) and the NP-completeness results are not affected by this particular flaw, so the damage is localized to the unit-interval contribution; nevertheless, the paper's headline result for unit interval graphs lacks a valid proof. This is a substantive mathematical error, not a stylistic or expositional concern, and it warrants rejection of the current version unless Theorem 8 can be corrected or the enumeration step in Theorem 17 can be justified without it.","tokens_in":27843,"tokens_out":44425,"duration_ms":453344,"concrete_test":"Verify the explicit counterexample computationally: build the sunflower graph with S=(s1s2, c, d), G1=(s1s2, s1p, pc, d), G2=(s1s2, qs1, qs2, qd, c). Enumerate all straight enumerations of G1 and G2, form the simultaneous enumeration ρ with shared order c<B<d (B={s1,s2}), compute loose components and reversible parts as defined in Section 3.3, and check whether reversing C1={c,p,s1,s2} yields a simultaneous enumeration. The check will fail. A broader test is to brute-force all connected sunflower proper interval graphs on up to 8 vertices and compare the set of simultaneous enumerations with those generated from one root by Theorem 8's reversal operations; any mismatch confirms the characterization is incorrect as stated.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 8 is load-bearing for Theorem 17: the unit-interval algorithm enumerates all candidate simultaneous enumerations by reversals of independent components and reversible parts from one initial enumeration. The definition of 'loose' in Section 3.3 says only that all vertices of S outside the component lie in one block of S; it does not restrict which blocks of S lie inside the component. Consequently a component can be 'loose' while containing vertices from two different blocks of S, and reversing it reverses the order of those two blocks in the shared order, destroying simultaneity.\n\nConcrete counterexample to the 'if' direction of Theorem 8: let the shared graph S have an edge s1s2 and isolated vertices c,d. Let G1 have edges s1s2, s1p, pc (and isolated d); let G2 have edges s1s2, qs1, qs2, qd (and isolated c). Both are proper interval graphs and the union is connected. The straight enumerations c<p<s1<s2 (with d after) in G1 and c<B<q<d with B={s1,s2} in G2 form a simultaneous enumeration ρ with shared order c<B<d. The component C1={c,p,s1,s2} of G1 is loose (the only outside shared vertex is d, one block) and is oriented at B, so C(B)={C1} is a reversible part. Reversing C1 gives shared order B<c<d in G1 while G2 remains c<B<d, so the tuple is not a simultaneous enumeration. This contradicts Theorem 8's assertion that reversal of a reversible part always gives a simultaneous enumeration. The proof of Theorem 8 does not cover the case where a component in C(B) contains another block B' of S, so the invalid step is hidden in exactly that omitted case.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies simultaneous proper and unit interval graphs in the sunflower case, where all input graphs share a common subgraph S. It presents a linear-time recognition algorithm for simultaneous proper interval graphs (Theorem 6) based on PQ-tree projection and intersection, followed by a partial representation extension. For simultaneous unit interval graphs, it develops a combinatorial characterization via chain-bar conflicts (Theorem 13) and an O(|V||E|) recognition algorithm (Theorem 17) that combines a characterization of all simultaneous enumerations (Theorem 8) with a 2-SAT search over reversals. The paper also proves NP-completeness for both recognition problems when the number of input graphs is not fixed and the sunflower restriction is dropped (Theorems 28 and 29).","tokens_in":28169,"tokens_out":15098,"duration_ms":155924,"significance":"If correct, the paper settles an open problem by giving the first polynomial-time algorithms for sunflower simultaneous proper and unit interval graphs with an unbounded number of input graphs, and it establishes tight complexity boundaries. The proper-interval recognition algorithm is elegant and robust, built on standard PQ-tree machinery and on the known partial representation extension algorithm of Klavík et al. The chain-bar conflict criterion and the reduction of the unit case to a 2-SAT instance are appealing and, if the supporting theorems are repaired, would constitute a substantial contribution. The NP-completeness reductions from Betweenness are straightforward and appear sound. However, the correctness of the unit-interval algorithm currently rests on Theorem 8, which is false as stated; this must be fixed before the main algorithmic claims can be accepted.","major_comments":[{"comment":"Theorem 8 is false as stated. Let S have vertices s1,s2,c,d and the single edge s1s2, so B={s1,s2}, {c}, {d} are its blocks. Let G1 have edges s1s2, s1p, pc and G2 have edges s1s2, qs1, qs2, qd. Both graphs are proper interval graphs, and the tuple (c<p<s1<s2<d, c<B<q<d) is a simultaneous enumeration: the shared block orders are c<s1<s2<d in G1 and c<B<d in G2. The component C1={c,p,s1,s2} of G1 is loose by the definition in Section 3.3, since the only shared vertex outside C1 is d, which forms a single block, and C1 is oriented at B, so C(B)={C1} is a reversible part. Reversing C1 yields the tuple (s2<s1<p<c<d, c<B<q<d), whose shared order in G1 is B<c<d and in G2 is c<B<d; this is not a simultaneous enumeration. This directly contradicts the 'if' direction of Theorem 8. The flaw is visible in the proof in Appendix B.5: it only treats shared-vertex pairs lying both inside the same block B or both outside the reversed component, and never a pair with one endpoint in B and another shared vertex in a different block that lies in the same component. The definition of 'loose' needs to be amended (e.g., require V_S∩C to be contained in one block of S), and Theorem 8 reproved. Because Theorem 17 uses Theorem 8 to restrict the candidate simultaneous enumerations searched by 2-SAT, this issue is load-bearing for the unit-interval algorithm.","section":"§3.3, definition of 'loose' and Theorem 8; Appendix B.5"},{"comment":"Lemma 18 is also false under the stated definition of 'loose'. The proof claims that when the shared order is unchanged, 'no straight enumeration containing vertices from more than one block of S is reversed'; but a component may contain vertices from several blocks of S while all shared vertices outside it lie in one block, and the current definition of 'loose' does not exclude that. The example in my first comment is exactly such a component: reversing the loose component C1 changes the shared order from c<B<d to B<c<d. The fix should make the 'loose' condition a property of the shared vertices inside the component, so that reversal of a loose component can never change the order of two blocks of S.","section":"Appendix B.3, Lemma 18"}],"minor_comments":[{"comment":"The statement of Theorem 13 appears twice with the same number, once after Corollary 12 and once after Lemma 16; the second occurrence should be renumbered.","section":"Section 4.1"},{"comment":"In Lemma 9, 'compatible with σ on V_i' is not formally defined for a fine enumeration σ of H; please state explicitly that the restriction of σ to V_i is the order to which ζ_i is compatible.","section":"Section 4.1, Lemma 9"},{"comment":"The notation C(B) is used both for the set of components oriented at block B and for the reversible part formed by such a set, which makes phrases like 'reversal of reversible part C(B)' ambiguous; consider using a different symbol for the part itself.","section":"Section 3.3"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the counterexample to Theorem 8 in my report is decisive and should be communicated clearly. The proposed redefinition of 'loose' seems local and likely repairs the theorem, so I recommend major revision rather than rejection. It would also be prudent to ask the authors to re-examine the scouting and zipping lemmas (Lemmas 22-25) for hidden assumptions about components that span more than one block of S."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, the proper-interval half of this paper is good; the unit-interval half is not reliable as written. The linear-time sunflower proper interval recognition (Theorem 6) is a clean application of PQ-tree projection plus Klavík et al.'s representation-extension algorithm, and I see no problem with it. The NP-hardness reductions in Appendix D are standard and the authors correctly note the overlap with Bok and Jedličková. The chain-bar conflict criterion is an interesting idea, and the O(|V||E|) algorithm would be a solid result if its foundations held.\n\nThey don't. Theorem 8, which is load-bearing for the unit case, is false as stated. The definition of loose only demands that all shared vertices outside the component lie in one block of S; it does not stop the component from containing several blocks of S. Reversing such a component reverses the order of those internal blocks in that graph, which can destroy simultaneity. Concrete example: S has edge s1s2 and isolated c,d. Let G1 be path c-p-s1-s2 plus isolated d, and G2 have edges s1s2, qs1, qs2, qd plus isolated c. Both are proper interval graphs, and σ1 = c<p<s1<s2<d, σ2 = c<{s1,s2}<q<d is a simultaneous enumeration with shared order c<{s1,s2}<d. The component C1 in G1 is loose and oriented at {s1,s2}, so by the definition C({s1,s2}) is a reversible part. But reversing C1 gives s2<s1<p<c<d, so the shared order in G1 becomes {s1,s2}<c<d while G2 stays c<{s1,s2}<d. That is not a simultaneous enumeration. So the 'if' direction of Theorem 8 fails. The proof only argues about pairs of shared vertices inside the block B; it silently ignores shared vertices outside B that the component may also contain.\n\nThat matters because Theorem 17 enumerates candidate simultaneous enumerations by reversals of reversible parts, and then applies the conflict test from Theorem 13. If the search space includes non-simultaneous tuples, the algorithm can either accept instances on the basis of an unrealizable enumeration or, more seriously, the completeness of the enumeration is unsupported. The scouting/zipping lemmas behind Theorem 13 are long appendix case analyses; given the bug in Theorem 8, I would want those re-audited too.\n\nBottom line: send it to review, but with a clear directive to fix or replace Theorem 8 and re-verify the unit algorithm. The proper interval result stands on its own and is worth publishing. I would not trust the unit interval theorem in its current form.","headline":"The proper-interval half of this paper is good; the unit-interval half is not reliable as written, because Theorem 8 is false as stated.","tokens_in":28706,"tokens_out":7004,"would_cite":true,"duration_ms":68439,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Simultaneous proper interval graphs with a shared induced subgraph are recognizable in linear time, unit versions in $O(|V|\\cdot|E|)$ time, and both are NP-complete without the shared subgraph.","keywords":["simultaneous representations","proper interval graphs","unit interval graphs","sunflower graphs","recognition algorithms","PQ-trees","graph sandwich problems","NP-completeness"],"falsifier":"Enumerate all connected sunflower graphs with, say, up to nine vertices and three input graphs, and compare the algorithm's verdict with an exact unit-interval checker that solves the linear program for equal-length intervals (or uses rational placement). One instance where the algorithm says 'yes' but no unit drawing exists, or says 'no' while a drawing exists, would refute the Theorem 13 characterization.","tokens_in":27635,"feed_emoji":"🧩","tokens_out":9757,"duration_ms":90729,"temperature":0.7,"pith_summary":"Simultaneous representations realize several graphs at once while keeping shared vertices identical; the sunflower case is the standard situation where every pair of graphs shares the same induced subgraph $S$. The paper establishes that, in this sunflower case, simultaneous proper interval graphs can be recognized and represented in linear time for any number of input graphs, and simultaneous unit interval graphs in $O(|V|\\cdot|E|)$ time on the union graph. Unit intervals are the rigid form: every unit representation is proper, but the converse fails, and the paper isolates the exact obstruction in a chain-bar conflict. It further shows the sunflower restriction is necessary, since both recognition problems are NP-complete when the number of graphs is part of the input and no common subgraph is imposed. If correct, the paper resolves the open sunflower complexity question for these two classes and leaves only the general sunflower interval-graph case open.","feed_headline":"Sunflower proper interval graphs recognized in linear time","feed_subtitle":"Unit-length version runs in O(|V||E|); drop the shared core and both turn NP-complete.","key_machinery":"The machinery is a chain of order-theoretic translations. PQ-trees encode all linear orders (fine enumerations) of each $G_i$; projecting them to the shared graph $S$ and intersecting the projections tests simultaneous proper interval representability. For the unit step, the paper introduces chains and bars: a $(u,v)$-chain is an ordered path from $u$ to $v$ inside one $G_i$, and a $(u,v)$-bar is an ordered independent set between them; a chain-bar conflict occurs when, for shared vertices $u,v$, one graph contributes a chain and another contributes a bar of the same size, making unit-length placement impossible. Scouting and zipping are two sweeps that extend the partial order induced by the simultaneous enumeration into a left-closed linear order, which is exactly a fine enumeration of a sandwich graph $H$ containing every $G_i$ as an induced subgraph; unit intervals are read off from that fine enumeration. The set of all possible simultaneous enumerations is described combinatorially by reversals of loose components organized into independent components and reversible parts.","core_discovery":"The central claim is a characterization-then-algorithm story. A sunflower simultaneous graph $G=(G_1,\\ldots,G_k)$ with shared induced subgraph $S$ has a simultaneous proper interval representation exactly when the graphs admit a simultaneous enumeration: straight enumerations of the $G_i$ that order the blocks of $S$ consistently. Such an enumeration exists iff the intersection of the PQ-trees of fine enumerations of the $G_i$ projected to $S$ is non-null, so recognition is linear-time. For unit intervals, Theorem 13 says a simultaneous enumeration $\\zeta$ is realizable by unit intervals iff no chain-bar conflict occurs: no ordered path in one $G_i$ and ordered independent set in another $G_j$ between two shared vertices have equal length. Since Theorem 8 describes every simultaneous enumeration as reversals of independent components and reversible parts of a given one, conflict-freeness can be searched by 2-SAT; Theorem 17 gives $O(|V|\\cdot|E|)$ recognition and representation. Finally, dropping the sunflower requirement and letting $k$ vary makes both problems NP-complete (Theorems 28 and 29).","pith_inferences":["The chain-bar distance argument does not need the sunflower assumption in its core inequality, so a plausible next step is to test the same conflict criterion on non-sunflower two-graph instances, where the representation space is not described by reversible parts but may still be closed under the same scouting-zipping sweeps.","If the scouting-zipping construction can be re-run with prescribed interval lengths instead of unit lengths, the same framework would yield a length-constrained simultaneous representation algorithm, with chain-bar conflicts replaced by weighted distance inequalities.","The Betweenness reductions suggest a wider pattern: any graph class whose local representation forces a vertex to lie between two others is likely to give NP-complete simultaneous recognition for unbounded $k$.","A natural stress test is to check whether the no-conflict criterion remains sufficient when the shared graph $S$ is disconnected; the paper assumes the union graph is connected without loss, but the unit-interval construction may behave differently across disconnected shared pieces."],"forward_implications":["The linear-time proper-interval test is optimal and constructive: a sunflower simultaneous graph that passes the PQ-tree test comes with a representation.","Unit-interval recognition handles any number of sunflower graphs in $O(|V|\\cdot|E|)$ time on the union graph.","The sunflower restriction is essential: without it, both recognition problems become NP-complete as soon as the number of graphs is part of the input.","The 2-SAT formulation yields a compact negative certificate: an unsatisfiable formula lists the reversal combinations that each contain a chain-bar conflict.","Both algorithms output an actual simultaneous representation, not only a decision, so they can be used as building blocks for drawing or verification tools."],"supporting_citations":[{"why":"Supplies the straight-enumeration characterization of proper interval graphs, the base of a simultaneous enumeration.","marker":"[11]"},{"why":"Provides the linear-time partial representation extension routine used to extend a shared representation of S to each Gi.","marker":"[21]"},{"why":"PQ-tree construction and intersection algorithms underpin the linear-time proper-interval test.","marker":"[7]"},{"why":"Shows proper and unit interval graphs are the same graph class, which the paper contrasts with the simultaneous setting.","marker":"[27]"},{"why":"Gives the fine-enumeration characterization that motivates the chain-bar and scouting-zipping arguments.","marker":"[22]"},{"why":"Establishes NP-completeness of simultaneous interval graph recognition; the paper's constructions borrow this reduction style.","marker":"[5]"},{"why":"Linear-time 2-SAT solver used to search reversal combinations for a conflict-free enumeration.","marker":"[2]"},{"why":"Betweenness problem, the source of the NP-hardness reductions for the non-sunflower cases.","marker":"[25]"}],"fun_headline_variants":["Sunflower interval graphs: linear proper, O(VE) unit recognition","Shared-core interval graphs: proper in linear, unit in O(VE)","Sunflower interval graphs: fast when the core is shared","Proper and unit interval graphs with common core: fast algorithms","Sunflower interval graphs: linear proper, O(VE) unit, else NP-hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The unit-interval algorithm rests on Theorem 13, the claim that a simultaneous enumeration admits a unit-length representation exactly when no chain-bar conflict exists; if that equivalence fails for some configuration, the 2-SAT search over reversal choices can certify the wrong answer.","fun_headline_variants_meta":{"raw":{"variants":["Sunflower interval graphs: linear proper, O(VE) unit recognition","Shared-core interval graphs: proper in linear, unit in O(VE)","Sunflower interval graphs: fast when the core is shared","Proper and unit interval graphs with common core: fast algorithms","Sunflower interval graphs: linear proper, O(VE) unit, else NP-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000268,"raw_usage":{"total_tokens":1635,"prompt_tokens":977,"completion_tokens":658,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":565}},"tokens_in":593,"tokens_out":658,"duration_ms":6500,"temperature":1.0,"reasoning_tokens":565,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:26:08.504172+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all connected sunflower graphs with, say, up to nine vertices and three input graphs, and compare the algorithm's verdict with an exact unit-interval checker that solves the linear program for equal-length intervals (or uses rational placement). One instance where the algorithm says 'yes' but no unit drawing exists, or says 'no' while a drawing exists, would refute the Theorem 13 characterization.","supporting_citations":[{"cited_title":"Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the straight-enumeration characterization of proper interval graphs, the base of a simultaneous enumeration."},{"cited_title":"Extending partial representations of proper and unit interval graphs","cited_arxiv_id":null,"evidence_quote":"Provides the linear-time partial representation extension routine used to extend a shared representation of S to each Gi."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows proper and unit interval graphs are the same graph class, which the paper contrasts with the simultaneous setting."},{"cited_title":"Optimal greedy algorithms for indifference graphs","cited_arxiv_id":null,"evidence_quote":"Gives the fine-enumeration characterization that motivates the chain-bar and scouting-zipping arguments."},{"cited_title":"A note on simultaneous representation problem for interval and circular-arc graphs","cited_arxiv_id":"1811.04062","evidence_quote":"Establishes NP-completeness of simultaneous interval graph recognition; the paper's constructions borrow this reduction style."},{"cited_title":"Total ordering problem","cited_arxiv_id":null,"evidence_quote":"Betweenness problem, the source of the NP-hardness reductions for the non-sunflower cases."}],"review_version":1}