{"id":"a2d77f27-6691-4351-be20-ff631d55bcf8","arxiv_id":"2607.05191","paper_version":1,"verdict":"ACCEPT","confidence":"UNKNOWN","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Two constrained recognition problems for oriented interval graphs are solved in linear time, improving a prior quadratic algorithm and solving the proper/unit case.","lead":"The paper gives linear-time algorithms to recognize oriented interval graphs when either the containment edges or the interval orientations are prescribed. This is a step toward a general recognition algorithm for a recently introduced graph class mixing directed and undirected edges.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The complexity bound on H+ is correct, and the algorithm avoids dense complement graphs via matching representations on H+ directly.","rationale":"The reader flagged the density of H+ as the load-bearing complexity concern. After careful tracing, the algorithm operates on H+ (the containment graph, which is sparse) rather than H+ (the complement, which could be dense). The modular decomposition, constraint checking, and matching representation computation all work on H+ directly. The bounds |V+| ≤ 2|V|, |E+_cont| ≤ |V|+|E|+|E⃗|, and |Γ| ∈ O(|E|+|E⃗|) are all correct, relying on the standard fact that the sum of maximal clique sizes in an interval graph is linear in |V|+|E|.\n\nI also checked whether Corollary 11's use in Theorem 3 could introduce an orientation mismatch (Lemma 7 computing a different feasible orientation than the given φ). This concern does not land because Corollary 11 uses the given φ directly in Theorem 10's conditions, adding clique order constraints to ≺_φ. Lemma 7 is only needed in Theorem 1 where the orientation is not prescribed.\n\nThe 'routine case analysis' in Theorem 10 is the most abbreviated step, but it is supported by the matching representation framework: a single matching representation of H+ simultaneously defines compatible transitive orientations of both H+ and H+ whose union is automatically a total order. The algorithm in Section B.1 verifies that the constraints on the matching representation are equivalent to conditions (i) and (ii).\n\nThe proofs of Lemmas 12, 18, 19, and 21 (the Section 4 machinery) are intricate but hold up under scrutiny. The P-node swap argument correctly uses the fact that consecutive children have no intervening intervals. The Q-node argument correctly applies Lemma 6 after verifying containment-only cross-edges. The linear-time algorithm in Lemma 21 has a correct amortized analysis using intrusive doubly-linked lists.\n\nThe paper makes a solid contribution with full proofs provided. The ACCEPT verdict is appropriate. Confidence should be higher than UNKNOWN given the completeness of the proofs.","tokens_in":31909,"tokens_out":32806,"duration_ms":614435,"concrete_test":"Independently verify the transitivity claim in Theorem 10: generate random permutation graphs H+, compute transitive orientations of H+ and H+ satisfying conditions (i) and (ii) via the constrained matching representation algorithm, and check that the union ≺_H+ ∪ ≺_H+ is a total order. If any counterexample is found where the union has a cycle, the interval construction in Theorem 10's proof would fail. Additionally, verify the bound Σ|C_i| ≤ |V|+|E| for interval graphs by computing maximal cliques on random interval graphs and summing their sizes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's concern is that the complement graph H+ might be too dense for linear-time processing. After tracing the argument, this concern does not land. The key insight is that the algorithm never explicitly constructs H+ (the complement). Instead, it works with H+ (the containment graph) directly, using Lemma 16's constrained matching representation algorithm, which runs in O(|V(H+)| + |E(H+)| + |Γ|) time. Here E(H+) = E+_cont, which is bounded by |V|+|E|+|E⃗| because the sum of maximal clique sizes in an interval graph is O(|V|+|E|) (each edge appears in at least one clique, each vertex in at least one). The constraint set Γ has size O(|E|+|E⃗|) because each arc contributes one placement constraint and each clique-vertex incidence contributes one constraint, totaling |E⃗| + Σ|C_i| = O(|E⃗|+|V|+|E|). The modular decomposition is also computed on H+ (not its complement), so the density of H+ is irrelevant.\n\nI also examined whether Corollary 11 (used in Theorem 3) might incorrectly substitute a computed feasible orientation for the given φ. The remark after Theorem 1 states that prescribing a clique order amounts to adding constraints (c_1,c_2),...,(c_{k-1},c_k) to ≺_φ in Theorem 10, where φ is the given orientation. The algorithm uses the given φ directly in Theorem 10's conditions, bypassing Lemma 7's orientation computation. This is correct: Theorem 10 characterizes φ-orientability for any given φ, feasible or not (infeasible φ simply fails the conditions).\n\nThe most abbreviated part of the proof is the 'routine case analysis' in Theorem 10 claiming the union of transitive orientations ≺_H+ and ≺_H+ is a total order. This is not automatically true for arbitrary pairs of transitive orientations of a graph and its complement. However, the algorithm in Section B.1 finds a single matching representation of H+ that simultaneously defines both orientations. For a matching representation (<L,<R), the orientation of H+ is <R ∩ >L and the orientation of H+ is <R ∩ <L; t","agreement_with_reader":"disagree"},"referee_report":{"model":"glm-5.2","summary":"This paper studies the recognition problem for oriented interval graphs, a class of mixed intersection graphs introduced by Gutowski et al. (GD 2022). An oriented interval representation assigns each interval a left or right orientation; overlapping same-orientation intervals yield arcs, while nested intervals and opposite-orientation overlaps yield undirected edges. The representation is determined combinatorially by a triple (φ, σ, E_cont) — orientation, clique ordering, and containment edges — whose mutual dependencies make recognition nontrivial. The authors characterize (i) orientations φ consistent with a given E_cont (Lemma 7) and (ii) clique orderings σ consistent with a given φ (via MPQ-tree constraints, Lemma 12). These yield two main algorithmic results: Theorem 1 gives a linear-time algorithm to decide whether G admits an oriented interval representation with prescribed containment edges E_cont (including E_cont = ∅, i.e., oriented proper/unit interval recognition, as Corollary 2), and Theorem 3 gives a linear-time algorithm for prescribed orientation φ. Both improve on the quadratic algorithm of Gutowski et al. for the uniform-orientation case. The key technical tools are augmented graphs G⁺, permutation graph characterizations (Theorem 10), constrained matching representations solved via modular decomposition (Lemma 16), and MPQ-tree rotations with a normalization step (Corollary 20).","tokens_in":32236,"tokens_out":691,"duration_ms":60941,"significance":"The paper makes a solid contribution to the structural and algorithmic theory of oriented interval graphs. The linear-time algorithms for two constrained recognition variants (Theorems 1 and 3) constitute genuine progress over the quadratic algorithm of Gutowski et al. [13], and Corollary 2 (oriented proper/unit interval recognition) is a clean corollary. The reduction to constrained matching representations on permutation graphs via the augmented graph G⁺ (Theorem 10, Lemma 16) is an elegant use of modular decomposition. The MPQ-tree constraint framework for Section 4 (Lemmas 18–19, Corollary 20) is well-motivated and the normalization argument is carefully structured. Full proofs are provided in the appendix for all starred lemmas and theorems. The complexity argument that H⁺ is not too dense (|E⁺_cont| ≤ |V|+|E|+|E⃗|, |Γ| ∈ O(|E|+|E⃗|)) is correct: the algorithm operates on H⁺ directly rather than its complement, and the bound follows from the structure of maximal cliques in interval graphs.","major_comments":[],"minor_comments":[],"recommendation":"minor_revision","confidential_remarks":"The paper is in good shape for a journal submission. The core technical content is sound and the proofs check out. The main work needed is presentation polish — the main body is dense and would benefit from better signposting, and there are several notation issues to clean up. I recommend minor revision. The reader's concern about the density of H⁺ does not land: the algorithm works on H⁺ directly (not its complement) via Lemma 16, and the size bounds are correctly argued in the proof of Theorem 1 in Section B.1."},"author_rebuttal":{"model":"glm-5.2","summary":"The referee report is highly positive, recommending minor revision with no specific major comments. The referee accurately summarizes the paper's contributions (Theorems 1 and 3, Corollary 2), validates the technical approach (augmented graph G+, permutation graph characterization, MPQ-tree constraints, modular decomposition), and confirms the complexity arguments. We thank the referee and note that no substantive changes are required.","responses":[{"response":"We thank the referee for the careful and accurate reading of our manuscript. The summary correctly captures the structure of our two main algorithmic results (Theorems 1 and 3), the role of the augmented graph G+ and the permutation graph characterization (Theorem 10), the constrained matching representation framework solved via modular decomposition (Lemma 16), and the MPQ-tree constraint framework (Lemmas 18–19, Corollary 20). We are pleased that the referee finds the complexity argument regarding the density of H+ correct, as this was a subtle point in our proof: the algorithm operates on H+ directly rather than its complement, and the bound |E+_cont| ≤ |V|+|E|+|E⃗| follows from the structure of maximal cliques in interval graphs.","revision_made":"no","referee_comment":"Overall assessment and recommendation of minor revision"},{"response":"Since the referee did not raise any specific major comments, we will use the opportunity to perform a careful proofreading pass on the manuscript to address any minor typographical or expositional issues before the final version. No substantive changes to the results, proofs, or algorithms are needed.","revision_made":"partial","referee_comment":"No major comments raised"}],"tokens_in":31501,"tokens_out":473,"duration_ms":13434,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"This paper solves two constrained recognition problems for oriented interval graphs in linear time: given a mixed graph with prescribed containment edges (Theorem 1), and given a mixed graph with prescribed orientation (Theorem 3). Both improve on prior work — Theorem 1 generalizes and speeds up a quadratic algorithm of Gutowski et al. (GD 2022), and Theorem 3 solves the proper/unit case as a corollary. The general recognition problem remains open, and the authors are honest about that. This is solid, well-executed work within its subfield. The structural characterizations are the real contribution: the description of feasible orientations via component-wise uniqueness up to reversal (Lemma 7), the reduction to constrained matching representations on the augmented containment graph H+ (Theorem 10), and the MPQ-tree constraints for clique orderings consistent with a given orientation (Lemma 12/18). The proofs are careful — necessity and sufficiency are argued separately, Example 14 explicitly shows Lemma 8's conditions are necessary but not sufficient, and the full proofs in the appendix are detailed. The linear-time claim for Theorem 1 initially looks suspicious because the complement of H+ could be dense. But the stress-test concern does not land: the algorithm never constructs the complement. It works with H+ directly via modular decomposition (Lemma 16), and the size bounds on E+_cont and the constraint set Gamma are justified by standard interval graph clique structure. The one spot that deserves scrutiny is the 'routine case analysis' in Theorem 10 claiming the union of the two transitive orientations is a total order. This is not automatic for arbitrary transitive orientations of a graph and its complement, but the argument works because the algorithm finds a single matching representation that simultaneously defines both orientations, which forces the union to be total. This could be stated more explicitly in the main text rather than left to the reader. The MPQ-tree constraint propagation in Section 4 is the densest part of the paper and the hardest to follow, but the proof structure is sound. This is for researchers working on intersection graph recognition and combinatorial algorithms. It deserves a serious referee who can verify the appendix proofs in detail, particularly the normalized representation argument (Lemma 19/Corollary 20) and the linear-time MPQ-tree construction (Lemma 21).","headline":"Two linear-time recognition algorithms for constrained oriented interval graphs; the general problem stays open","tokens_in":33072,"tokens_out":526,"would_cite":true,"duration_ms":47316,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Linear-time recognition of oriented interval graphs","keywords":[],"falsifier":"A family of mixed graphs where the augmented containment graph H+ has a super-linear number of edges, which would break the linear-time complexity argument for the matching representation algorithm.","tokens_in":32065,"feed_emoji":"📐","tokens_out":584,"duration_ms":51539,"temperature":0.7,"pith_summary":"This paper studies the recognition of oriented interval graphs — intersection graphs of intervals on the line where each interval is oriented left or right, producing a mixed graph with both directed arcs and undirected edges. The authors prove two main results. First, given a mixed graph G and a prescribed set of containment edges E_cont, there is a linear-time algorithm deciding whether G admits an oriented interval representation where precisely those edges are represented by interval containment (Theorem 1). Second, given G and a prescribed orientation phi, there is a linear-time algorithm deciding whether G admits an oriented interval representation with that orientation (Theorem 3). Both results improve a prior quadratic-time algorithm and, as a corollary, solve the recognition problem for oriented proper (or unit) interval graphs in linear time.","feed_headline":"Linear-time recognition for oriented interval graphs","feed_subtitle":"Two constrained recognition problems solved in linear time, improving prior quadratic algorithms and settling oriented proper interval graph","key_machinery":"oriented interval representation, mixed graph, containment edges, clique ordering, orientation, permutation graph, matching representation, MPQ-tree, modular decomposition","core_discovery":"The central mechanism is a structural decomposition of the three interdependent parameters of an oriented interval representation — orientation phi, clique ordering sigma, and containment edge set E_cont — into pairwise consistency conditions. For prescribed containment edges, the authors show that a feasible orientation is determined component-wise in G minus E_cont (unique up to reversal per connected component), and the remaining question reduces to a constrained matching representation problem on the complement of an augmented containment graph H+, solvable in linear time via modular decomposition. For prescribed orientation, the authors characterize which clique orderings are consistent","pith_inferences":[],"forward_implications":["Oriented proper and oriented unit interval graphs can now be recognized in linear time, settling the computational complexity of these graph classes.","The structural characterizations of how orientation, clique ordering, and containment edges constrain each other provide a roadmap for the general recognition problem where none of the three parameters is prescribed.","The constrained matching representation framework on augmented containment graphs may extend to other intersection graph classes involving nested or directed geometric objects.","The linear-time algorithms make oriented interval graph recognition practical for large-scale inputs in scheduling or network visualization contexts where mixed directed/undirected relationships arise."],"fun_headline_variants":["Linear-time recognition for two constrained oriented interval graph problems","Oriented proper interval graphs recognized in linear time","Quadratic to linear: faster oriented interval graph recognition","Structural decomposition enables linear-time oriented interval recognition","Prescribed orientation or containment edges yield linear-time recognition"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The linear-time complexity claim for Theorem 1 depends on the augmented containment graph H+ having edge count bounded by O(|V|+|E|+|E_arrow|), which ensures the complement graph is not too dense for the modular decomposition step to run in linear time.","fun_headline_variants_meta":{"raw":{"variants":["Linear-time recognition for two constrained oriented interval graph problems","Oriented proper interval graphs recognized in linear time","Quadratic to linear: faster oriented interval graph recognition","Structural decomposition enables linear-time oriented interval recognition","Prescribed orientation or containment edges yield linear-time recognition","Pairwise consistency conditions crack oriented interval graph recognition","Linear-time recognition when containment edges or orientation are fixed","Characterizing consistency across orientation, ordering, and containment","Oriented interval recognition in linear time via modular decomposition","Constrained recognition of oriented interval graphs improved to linear time"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":941,"prompt_tokens":620,"completion_tokens":321,"prompt_tokens_details":null},"tokens_in":620,"tokens_out":321,"duration_ms":4651,"temperature":1.0,"reasoning_tokens":252,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T00:07:25.943439+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A family of mixed graphs where the augmented containment graph H+ has a super-linear number of edges, which would break the linear-time complexity argument for the matching representation algorithm.","supporting_citations":[],"review_version":1}