Pith. sign in

REVIEW 2 major objections 7 minor 38 references

Practical approach to $2$-Euclidean Preferences

T0 review · 2 major / 7 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper establishes a graph-theoretic obstruction—the controversity graph of a 2-Euclidean election has maximum degree at most two and any cycle is connected—and uses it, with reduction rules and ILP/QCP solvers, to classify almost all…

desk verdict A practical, mostly sound toolkit for refuting 2-Euclidean preferences, but the ILP's 4-cycle constraint is incorrect and can reject true 2-Euclidean elections. read the letter →

arxiv 2502.07454 v1 pith:MXM2HHRG submitted 2025-02-11 cs.GT

Michal Dvořák , Dušan Knop , Jan Pokorný , Martin Slávik This is my paper · ORCID
classification cs.GT
keywords 2-EuclideanpreferencesEuclideanembeddingforbiddensubstructurescontroversitygraphconvexhullintegerlinearprogrammingquadraticallyconstrainedPrefLib
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to make the recognition of 2-Euclidean elections practical, despite the problem being ∃R-complete in general. Its main theoretical contribution is a new class of forbidden substructures: in any 2-Euclidean election, the corresponding controversity graph must have maximum degree at most two, and if it contains a cycle, that cycle must be the whole connected component. This gives a fast refutation test that, together with the known 3-8 pattern, reduction rules, and ILP/QCP solvers, resolves most real-world preference data in under a second.

What carries the argument

The controversity graph CG(C,V) has a vertex for each voter who is uniquely on one side of some candidate-pair bisector, and an edge for each pair of voters that are jointly on one side of a bisector. In a nice 2-Euclidean embedding these vertices must occupy the convex hull of the voter set and edges encode consecutiveness on that hull, forcing the graph to be a path, a cycle, or a disjoint union of paths—hence the degree and connectivity restrictions. The ILP adds further combinatorial constraints drawn from the region-count upper bound, the embedding graph's distance-preserving structure, and bisector-crossing bounds.

What would settle it

Take one of the 60 unresolved PrefLib instances, run the QCP solver with growing bounding boxes until it returns an explicit 2-Euclidean embedding, then compute the controversity graph; if the graph has a vertex of degree at least 3 or a cycle plus another component, Theorem 3.4 is false. A direct computer search over verified 2-Euclidean elections on five candidates looking for such a graph would also settle the theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.4: if an election is 2-Euclidean, then its controversity graph CG(C,V) has maximum degree at most 2 and, if it contains a cycle, the graph is connected. Consequently, an election whose controversity graph has a vertex of degree at least 3, or a cycle plus any other component, is immediately certified as not 2-Euclidean. The proof runs through a nice 2-Euclidean embedding, where controversial voters must lie on the convex hull and controversial pairs must be consecutive on it.

Load-bearing premise

Everything rests on Theorem 2.8's guarantee of a nice 2-Euclidean embedding—in particular Lemma 2.6's claim that parallel bisectors can always be perturbed away, which the paper argues informally by analogy with Lemma 2.5; if a boundary case defeats that perturbation, the convex-hull refutation loses its foundation.

Editorial extensions

If this is right

  • An election whose controversity graph has a degree-3 vertex or a disconnected cycle is provably not 2-Euclidean, and this refutation can be checked in polynomial time by scanning candidate pairs and voter triples.
  • The hull-based refutation, restricted in practice to four-voter subelections, matches the full version on all PrefLib instances, suggesting that small voter subsets capture most real-world convex-hull obstructions.
  • The reduction rules preserve 2-Euclideanness and removed 1,729 candidates across 802 PrefLib instances, making many previously hard instances tractable for the EST baseline as well.
  • The improved QCP formulation with a growing bounding box supplies yes-certificates, solving 39 nontrivial yes-instances that no other component could handle.
  • Combining all components lowers the number of unresolved PrefLib instances from 343 to 60, with 98.7% of instances resolved in under one second.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • My inference: the empirical equivalence of Hull and Hull++ hints that, on PrefLib-sized profiles, checking all four-voter subelections may capture every convex-hull obstruction; proving this would yield a polynomial-time no-certificate for a wide class of real-world elections.
  • My inference: if the paper's conjecture that Reduction Rule 1+ cannot remove more than three copied tail-block candidates is correct, then the block-copy reduction is exactly tight, and any extension would need a fundamentally different construction.
  • My inference: the convex-hull approach may generalize to d-Euclidean elections through controversial subsets mapped to faces of the higher-dimensional convex hull; the paper leaves this open, but a degree-bound analogue would likely give a similar practical refutation test.
  • My inference: the ILP's lazy variable creation, beginning with the actual votes and adding permutations only as needed, may itself be a reusable pattern for other ∃R-complete recognition problems where the search space is factorial.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 7 minor

Summary. The paper presents a practical toolkit for deciding whether a given preference profile is 2-Euclidean. It introduces a new forbidden-substructure refutation based on the controversity graph of voters (Theorem 3.4), several candidate-reduction rules with explicit solution lifting, an ILP that encodes necessary conditions on the embedding graph, and a QCP formulation with an epsilon-scaling bounding-box scheme. Experiments on PrefLib report that the combined pipeline reduces the number of unresolved instances from 343 to 60 and resolves 98.7% of instances in under one second. The main theoretical claims are Theorem 3.4 (convex-hull refutation), Theorem 5.21 (correctness of the ILP constraints), and Lemma 6.2 (QCP equivalence); most proofs are constructive, and the experimental comparison with the EST algorithm is thorough.

Significance. If the results hold, this is a useful practical advance in recognizing 2-Euclidean preferences. The reduction rules are proven correct with explicit embedding-lifting algorithms, the QCP epsilon-scaling equivalence is proved cleanly, and the benchmark study is extensive and directly compares with the previous EST algorithm. The main caveat is that one load-bearing perturbation lemma, Lemma 2.6, is only sketched; a complete proof is needed before the 'nice embedding' framework supporting the ILP can be regarded as fully sound. I also examined the alleged counterexample to ILP constraint (15) based on four concyclic candidates; it does not survive scrutiny, because if all four permutations in a tuple from C_{ab|cd}(v) are nonempty, Observation 5.3 forces them to form a 4-cycle in the embedding graph. The proof of (15) should nevertheless be written out more carefully, since the current one-sentence justification is too terse.

major comments (2)
  1. [Section 2.6 (Lemma 2.6)] The proof of Lemma 2.6 is only a sketch. The sentence 'by similar arguments as in Lemma 2.5 we can ensure that no triplets of candidates become collinear and no pair of bisectors becomes a parallel pair' omits the central argument: one must show that a sufficiently small perpendicular movement of candidate a exists that simultaneously preserves all nonempty regions, avoids all positions that create a collinear candidate triple, avoids all positions that create a new parallel pair, and strictly reduces the number of parallel pairs. Because Theorem 2.8 and hence the ILP section's use of 'nice' embeddings depend on this lemma, please provide a complete argument, including an explicit description of the finite set of forbidden positions and a proof that it cannot cover the allowable open region.
  2. [Section 5.3.1, Eq. (15)] The correctness argument for constraint (15) is too terse as written. The text says that two bisectors intersect at most once and therefore there is at most one 4-cycle for the pair, but it does not address the possibility of three or more concurrent bisectors. I checked the proposed concyclic counterexample and it does not invalidate the constraint: if all four permutations v, v∘τ_ab, v∘τ_cd, and v∘τ_ab∘τ_cd are nonempty, then each consecutive pair in the 4-tuple differs by a consecutive swap, so by Observation 5.3 the four vertices form a 4-cycle in D_γ; two such 4-cycles for the same pair of bisectors would force the two bisectors to intersect twice. The proof should nevertheless be expanded to state this explicitly, since Theorem 5.21 certifies the soundness of the whole ILP.
minor comments (7)
  1. [Abstract] The phrase 'we propose practical approach' should read 'we propose a practical approach'.
  2. [Section 2.6 (Lemma 2.4)] The phrase 'has nonzero (possibly infinite) measure' is informal; it would be clearer to say that the region has nonempty interior and hence positive area, possibly infinite.
  3. [Section 5.1.1 (Lemma 5.11)] The term 'opposite arc' is used without a formal definition; please define it in terms of the cyclic order of the intersection points on the bounding circle.
  4. [Section 5.3.1] The sentence 'Observe that if we sum over all distinct constraints of the form (15)' is confusing; I suggest rephrasing to 'Consider all constraints of the form (15), one for each 4-subset of candidates.'
  5. [Section 7.2] There is a typo: 'the constrains with the sum' should be 'the constraints with the sum'.
  6. [Section 7.3 / Figures 12 and 16] The per-dataset table and the solver-combination figure are information-dense and hard to parse; splitting the table or using clearer column headers would improve readability.
  7. [Section 7] The paper does not mention availability of code or data; providing a repository would strengthen the reproducibility of the experimental claims.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation chain is self-contained and benchmarked externally, and the ILP (15) concern is a soundness issue, not a circular one.

full rationale

The paper's central refutation tools are derived from first principles rather than fitted to the conclusion. Theorem 3.4 follows from Lemmas 3.2 and 3.3, which translate the geometric fact that a controversial voter lies on the convex hull and controversial singleton pairs are consecutive; these lemmas are proved from the definition of a nice 2-Euclidean embedding, not assumed. The ILP constraints (1)-(15) are each justified by a lemma (e.g., Lemmata 5.14-5.20) showing that any nice 2-Euclidean embedding satisfies them, and the paper explicitly states the direction is one-way (Section 5.2: 'Not every feasible solution to the ILP should correspond to some embedding'), so the ILP is used only as a sound refuter, not as a definition of the property. The QCP approach (17)-(19) is a direct relaxation of the definition of a 2-Euclidean embedding; Lemma 6.1 and Lemma 6.2 prove that the epsilon modification and squared-distance form are equivalent for any positive epsilon, so the hand-chosen epsilon*=1 is not load-bearing. Reduction Rules 1+, 1++, and 2 are proven correct with constructive embeddings; they are not fitted parameters. Experimental claims (343 to 60 unresolved, 98.7% under one second) are measured against the external PrefLib dataset, and improvements are compared with the independent EST algorithm [17]; no fitted value is renamed as a prediction. The use of external results (Bennett-Hays region count, Bulteau-Chen 7-candidate bound, Kamiya-Takemura-Terao 4-candidate characterization, Bogomolnaia-Laslier 3-8 pattern) is real independent support, and no load-bearing premise rests on a self-citation. The reviewer's counterexample to constraint (15) alleges an unsound ILP constraint that can reject a genuine 2-Euclidean election; that is a mathematical correctness issue (a false no-certificate), not circularity, because the constraint is not equivalent to its input by construction and the paper does not fit it to the output. Under the stated rules, incorrectness without input-output identity is outside the circularity finding, so the appropriate score is 0.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No free parameter is fitted to data; two implementation parameters are hand-chosen and explicitly non-load-bearing. Theoretical results rely on standard external results in hyperplane arrangements, the 4-candidate characterization, and the Bulteau-Chen theorem. The controversity graph is a defined combinatorial object, not a postulated entity.

free parameters (2)
  • Hull subset size = 4
    Implementation of the Hull heuristic checks only subelections with 4 voters. The paper states this is empirically sufficient on PrefLib, and Hull++ (which checks all subsets) confirms the same solved instances, so the choice is a heuristic, not a fitted constant.
  • QCP error term epsilon* = 1
    The squared-distance gap in the QCP is fixed to 1. Lemma 6.2 shows any positive epsilon* works, so this is a normalization choice rather than a parameter fitted to data.
assumptions (4)
  • standard math Bennett-Hays formula for the maximum number of regions induced by m candidate points in R^2 (Corollary 5.1)
    Used in ILP constraint (2) to limit the number of nonempty regions to ub(|C|). The paper cites [2] and reproduces the closed form, but does not prove the formula itself.
  • standard math Bulteau-Chen results: any election with at most 2 voters is 2-Euclidean; any election with 3 voters and at most 7 candidates is 2-Euclidean; and the 3-8 pattern is not 2-Euclidean
    Used to justify the trivial solver and the 3-8 forbidden pattern (Lemma 2.9). Cited from [7] and the underlying construction by [4].
  • standard math Kamiya-Takemura-Terao characterization of maximal 2-Euclidean profiles for 4 candidates
    Used in Section 7 to skip candidate subsets of size 4 in the ILP, relying on the complete characterization of 4-candidate 2-Euclidean elections from [23].
  • domain assumption Gurobi solver correctness for ILP and QCP
    All refutation and embedding results depend on the solver returning correct feasible or infeasible answers; the paper uses Gurobi [20] with timeouts and does not provide independent certificates.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Practical approach to $2$-Euclidean Preferences." pith.science (2026). https://pith.science/paper/MXM2HHRG

@misc{pith2026250207454,
  author       = {Pith},
  title        = {Pith review of: Practical approach to $2$-Euclidean Preferences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MXM2HHRG}},
  note         = {Machine review of arXiv:2502.07454}
}
abstract

An election is a pair $(C,V)$ of candidates and voters. Each vote is a ranking (permutation) of the candidates. An election is $d$-Euclidean if there is an embedding of both candidates and voters into $\mathbb{R}^d$ such that voter $v$ prefers candidate $a$ over $b$ if and only if $a$ is closer to $v$ than $b$ is to $v$ in the embedding. For $d\geq 2$ the problem of deciding whether $(C,V)$ is $d$-Euclidean is $\exists \mathbb{R}$-complete. In this paper, we propose practical approach to recognizing and refuting $2$-Euclidean preferences. We design a new class of forbidden substructures that works very well on practical instances. We utilize the framework of integer linear programming (ILP) and quadratically constrained programming (QCP). We also introduce reduction rules that simplify many real-world instances significantly. Our approach beats the previous algorithm of Escoffier, Spanjaard and Tydrichov\'a~[Algorithmic Recognition of 2-Euclidean Preferences, ECAI 2023] both in number of resolved instances and the running time. In particular, we were able to lower the number of unresolved PrefLib instances from $343$ to $60$. Moreover, $98.7\%$ of PrefLib instances are resolved in under $1$ second using our approach.

Figures

Figures reproduced from arXiv: 2502.07454 by the authors.

Figure 1
Figure 1. Examples of transformations. On the left, the solid triangle [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. The graph of permutations 𝐺(S𝐶) for 𝐶 = {𝑎, 𝑏, 𝑐, 𝑑} realised in the shape of a truncated octahedron. The edges of the graph correspond to consecutive swaps. Note that the distance 𝑑 swap coincides with the graph-theoretical distance 𝑑𝐺 (S𝐶 ) . For example we have 𝑑 swap (𝑎𝑏𝑐𝑑, 𝑑𝑏𝑐𝑎) = 5 because 𝑑𝑏𝑐𝑎 = 𝑎𝑏𝑐𝑑 ◦ 𝜏𝑎,𝑏 ◦ 𝜏𝑎,𝑐 ◦ 𝜏𝑎,𝑑 ◦ 𝜏𝑐,𝑑 ◦ 𝜏𝑏,𝑑 and 𝑑𝑏𝑐𝑎 cannot be expressed as composition of 𝑎𝑏𝑐𝑑 with fewer than 5 conse… view at source ↗
Figure 3
Figure 3. A 2-Euclidean embedding of the election (𝐶,𝑉 ) with 𝐶 = {𝑎, 𝑏, 𝑐, 𝑑} and 𝑉 = {𝑏𝑑𝑎𝑐, 𝑏𝑎𝑐𝑑, 𝑎𝑑𝑐𝑏, 𝑎𝑐𝑑𝑏, 𝑑𝑎𝑐𝑏, 𝑐𝑎𝑑𝑏, 𝑏𝑐𝑎𝑑}. The dashes lines are the bisectors between pairs of candidates. The shaded triangle is the region 𝑅 𝛾 (𝑎𝑑𝑏𝑐). Note that for example the region 𝑅 𝛾 (𝑐𝑑𝑏𝑎) is empty. that (𝑇 ◦ 𝛾) (𝑥1) = 𝑝1 and (𝑇 ◦ 𝛾) (𝑥2) = 𝑝2. In particular for any four elements 𝑦1, 𝑦2, 𝑦3, 𝑦4 ∈ 𝑋 we have ℓ2 (𝛾 (𝑦1 ),𝛾 (𝑦2 ) ) ℓ2 … view at source ↗
Figures from the paper (13 more)
Figure 4
Figure 4. Figure 4: The 3-8 pattern. Lemma 2.9. Given an election (𝐶,𝑉 ), we can in 𝑂(|𝑉 | 3 |𝐶| 2 ) time decide whether (𝐶,𝑉 ) contains the 3-8 pattern. Proof. Fix {𝑣1, 𝑣2, 𝑣3} ⊆ 𝑉 and fix one of the candidates in 𝐶 as 𝑐 ∅. For any other candidate 𝑑 ∈ 𝐶\{𝑐 ∅ } compute the vector 𝑥𝑑 = (𝑥1…
Figure 5
Figure 5. Figure 5: The situation in the proof of Lemma 3.3. [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: Situation in the proof of correctness of Reduction Rule 1 [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: Visualisation of the proof of Lemma 4.5. [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]
Figure 8
Figure 8. Figure 8: The situation in Reduction Rule 2. The blue open ball is the feasible region [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]
Figure 9
Figure 9. Figure 9: The three subcases in Case 2 in the proof of Reduction Rule 2. The black line is the line [PITH_FULL_IMAGE:figures/full_fig_p021_9.png]
Figure 10
Figure 10. Figure 10: The line 𝐿2𝑘−1,2𝑘 separates the voters with respect to their preference about candidates 𝑐2𝑘−1𝑐2𝑘 . For example 𝑣1 is the only candidate that prefers 𝑐2 over 𝑐1, thus 𝐿1,2 separates 𝛾 (𝑣1) from 𝛾 (𝑣2),𝛾 (𝑣3),𝛾 (𝑣4). We now describe how to embed the candidates. The aim…
Figure 11
Figure 11. Figure 11: The embedding graph D𝛾 (in black). Note that the unbounded regions 𝑅 𝛾 (𝑣) (or equivalently the vertices on the outer face of D𝛾 ) are in one to one correspondence with the circular arcs of the circle induced by the bisectors. For example the highlighted circular arc …
Figure 12
Figure 12. Figure 12: Solved instances per PrefLib dataset by using all solvers combined (including EST). The green numbers [PITH_FULL_IMAGE:figures/full_fig_p036_12.png]
Figure 13
Figure 13. Figure 13: The figure shows which solver was first to solve a given instance with up to [PITH_FULL_IMAGE:figures/full_fig_p037_13.png]
Figure 15
Figure 15. Figure 15: Running times of individual algorithms. First [PITH_FULL_IMAGE:figures/full_fig_p038_15.png]
Figure 17
Figure 17. Figure 17: Unsolved instances with at least 4 votes. [PITH_FULL_IMAGE:figures/full_fig_p038_17.png]
Figure 17
Figure 17. Figure 17: Notably, these unsolved instances are relatively small, they have at most [PITH_FULL_IMAGE:figures/full_fig_p039_17.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 31 canonical work pages

  1. [1]

    Ballester and Guillaume Haeringer

    Miguel A. Ballester and Guillaume Haeringer. 2011. A characterization of the single-peaked domain. Social Choice and Welfare 36, 2 (01 Feb 2011), 305–322. https://doi.org/10.1007/s00355-010-0476-3

    work page doi:10.1007/s00355-010-0476-3 2011

  2. [2]

    Bennett and William L

    Joseph F. Bennett and William L. Hays. 1960. Multidimensional unfolding: Determining the dimensionality of ranked preference data. Psychometrika 25, 1 (01 Mar 1960), 27–43

    work page 1960

  3. [3]

    Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist, Tillmann Miltzow, and Simon Weber. 2023. The Complexity of Recognizing Geometric Hypergraphs. In Graph Drawing and Network Visualization , Michael A. Bekos and Markus Chimani (Eds.). Springer Nature Switzerland, 163–179

    work page 2023

  4. [4]

    Anna Bogomolnaia and Jean-Francois Laslier. 2007. Euclidean preferences. Journal of Mathematical Economics 43, 2 (February 2007), 87–98

    work page 2007

  5. [5]

    Robert Bredereck, Jiehua Chen, and Gerhard Woeginger. 2013. A characterization of the single-crossing domain. Social Choice and Welfare 41, 4 (October 2013), 989–998. https://doi.org/10.1007/s00355-012-0717-8

    work page doi:10.1007/s00355-012-0717-8 2013

  6. [6]

    Anna Bretscher, Derek Corneil, Michel Habib, and Christophe Paul. 2008. A Simple linear time LexBFS cograph recognition algorithm. SIAM Journal on Discrete Mathematics 22, 4 (2008), 1277 – 1296. https://doi.org/10.1137/ 060664690

    work page 2008

  7. [7]

    Laurent Bulteau and Jiehua Chen. 2022. 2-Dimensional Euclidean Preferences. arXiv:2205.14687 [cs.GT]

    work page Pith review arXiv 2022

  8. [8]

    Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber. 2018. Intersection Graphs of Rays and Grounded Segments. Journal of Graph Algorithms and Applications 22, 2 (2018), 273–294. https: //doi.org/10.7155/jgaa.00470

    work page doi:10.7155/jgaa.00470 2018

Show all 38 references
  1. [9]

    Jiehua Chen, Martin Nöllenburg, Sofia Simola, Anaïs Villedieu, and Markus Wallinger. 2022. Multidimensional Manhattan Preferences. arXiv:2201.09691 [cs.MA]

    2022 arXiv

  2. [10]

    Woeginger

    Jiehua Chen, Kirk Pruhs, and Gerhard J. Woeginger. 2015. The one-dimensional Euclidean domain: Finitely many obstructions are not enough. CoRR abs/1506.03838 (2015). arXiv:1506.03838 http://arxiv.org/abs/1506.03838

    2015 arXiv

  3. [11]

    Derek G. Corneil. 2004. A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Applied Mathematics 138, 3 (2004), 371 – 379. https://doi.org/10.1016/j.dam.2003.07.001

    2004 doi

  4. [12]

    Doignon and J.C

    J.P. Doignon and J.C. Falmagne. 1994. A Polynomial Time Algorithm for Unidimensional Unfolding Representations. Journal of Algorithms 16, 2 (1994), 218–233. https://doi.org/10.1006/jagm.1994.1010

    1994

  5. [13]

    Saari Donald G. 2011. Chapter Twenty-Seven - Geometry of Voting. InHandbook of Social Choice and Welfare, Kenneth J. Arrow, Amartya Sen, and Kotaro Suzumura (Eds.). Handbook of Social Choice and Welfare, Vol. 2. Elsevier, 897–945. https://doi.org/10.1016/S0169-7218(10)00027-4

    2011 doi

  6. [14]

    Edith Elkind and Piotr Faliszewski. 2014. Recognizing 1-Euclidean Preferences: An Alternative Approach. InAlgorithmic Game Theory

    2014

  7. [15]

    Edith Elkind, Martin Lackner, and Dominik Peters. 2022. Preference restrictions in computational social choice: A survey . Technical Report. arXiv preprint arXiv:2205.09092

    2022 arXiv

  8. [16]

    Bruno Escoffier, Olivier Spanjaard, and Magdaléna Tydrichová. 2022. Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences. Discret. Appl. Math. 318 (2022), 6–12. https://doi.org/10.1016/J. DAM.2022.05.009

    2022 doi

  9. [17]

    Bruno Escoffier, Olivier Spanjaard, and Magdaléna Tydrichová. 2023. Algorithmic Recognition of 2-Euclidean Prefer- ences. In ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland - Including 12th Conference on Prestigio...

    2023 doi

  10. [18]

    Bruno Escoffier, Olivier Spanjaard, and Magdaléna Tydrichová. 2022. Euclidean preferences in the plane underℓ1,ℓ2 andℓ∞ norms. arXiv:2202.03185 [math.MG]

    2022 arXiv

  11. [19]

    I.J Good and T.N Tideman. 1977. Stirling numbers and a geometric ,structure from voting theory. Journal of Combinatorial Theory, Series A 23, 1 (1977), 34–45. https://doi.org/10.1016/0097-3165(77)90077-2

    1977 doi

  12. [20]

    Gurobi Optimization, LLC. 2024. Gurobi Optimizer Reference Manual. https://www.gurobi.com

    2024

  13. [21]

    Thekla Hamm, Martin Lackner, and Anna Rapberger. 2021. Computing Kemeny Rankings from d-Euclidean Preferences. In Algorithmic Decision Theory - 7th International Conference, ADT 2021, Toulouse, France, November 3-5, 2021, Proceedings (Lecture Notes in Computer Science, Vol. 13...

    2021 doi

  14. [22]

    Hays and Joseph F

    William L. Hays and Joseph F. Bennett. 1961. Multidimensional unfolding: Determining configuration from complete rank order preference data. Psychometrika 26, 2 (01 Jun 1961), 221–238. https://doi.org/10.1007/BF02289716

    1961 doi

  15. [23]

    Hidehiko Kamiya, Akimichi Takemura, and Hiroaki Terao. 2011. Ranking patterns of unfolding models of codimension one. Adv. Appl. Math. 47, 2 (2011), 379–400. https://doi.org/10.1016/J.AAM.2010.11.002

    2011 doi

  16. [24]

    Ross Kang and Tobias Müller. 2012. Sphere and Dot Product Representations of Graphs. Discrete & Computational Geometry 47, 3 (2012), 548–569. https://doi.org/10.1007/s00454-012-9394-8

    2012 doi

  17. [25]

    Vicki Knoblauch. 2010. Recognizing one-dimensional Euclidean preference profiles. Journal of Mathematical Economics 46, 1 (2010), 1–5. https://doi.org/10.1016/j.jmateco.2009.05.007 Michal Dvořák, Jan Pokorný, Dušan Knop, and Martin Slávik 39

    2010 doi

  18. [26]

    Jan Kratochvíl. 1991. String graphs. II. Recognizing string graphs is NP-hard. Journal of Combinatorial Theory, Series B 52, 1 (1991), 67–78

    1991

  19. [27]

    Jan Kratochvíl and Jiří Matoušek. 1994. Intersection graphs of segments. Journal of Combinatorial Theory. Series B 62, 2 (1994), 289–315. https://doi.org/10.1006/jctb.1994.1071

    1994

  20. [28]

    Casimir Kuratowski. 1930. Sur le problème des courbes gauches en Topologie. Fundamenta Mathematicae 15, 1 (1930), 271–283

    1930

  21. [29]

    Lekkeikerker and J

    C. Lekkeikerker and J. Boland. 1962. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae 51, 1 (1962), 45–64

    1962

  22. [30]

    McConnell

    Nathan Lindzey and Ross M. McConnell. 2013. On Finding Lekkerkerker-Boland Subgraphs. ArXiv abs/1303.1840 (2013). https://api.semanticscholar.org/CorpusID:14898595

    2013 arXiv

  23. [31]

    Jiří Matoušek. 2014. Intersection graphs of segments and ∃R. ArXiv 1406.2636 (2014)

    2014 arXiv

  24. [32]

    Nicholas Mattei and Toby Walsh. 2013. PrefLib: A Library of Preference Data http://preflib.org. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT 2013) (Lecture Notes in Artificial Intelligence) . Springer

    2013

  25. [33]

    Martin Milanič, Romeo Rizzi, and Alexandru I. Tomescu. 2014. Set graphs. II. Complexity of set graph recognition and similar problems. Theoretical Computer Science 547 (2014), 70–81. https://doi.org/10.1016/j.tcs.2014.06.017

    2014 doi

  26. [34]

    Tobias Müller, Erik Jan van Leeuwen, and Jan van Leeuwen. 2013. Integer representations of convex polygon intersection graphs. SIAM Journal on Discrete Mathematics 27, 1 (2013), 205–231. https://doi.org/10.1137/110825224

    2013 doi

  27. [35]

    Dominik Peters. 2017. Recognising Multidimensional Euclidean Preferences. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA , Satinder Singh and Shaul Markovitch (Eds.). AAAI Press, 642–648. https:...

    2017 doi

  28. [36]

    Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. 2003. Recognizing string graphs in NP. J. Comput. System Sci. 67, 2 (2003), 365–380. https://doi.org/10.1016/S0022-0000(03)00045-X Special Issue on STOC 2002

    2003 doi

  29. [37]

    Klaus Simon. 1991. A new simple linear algorithm to recognize interval graphs. In Computational Geometry-Methods, Algorithms and Applications: International Workshop on Computational Geometry CG’91 Bern, Switzerland, March 21–22, 1991 Proceedings. Springer, 289–308

    1991

  30. [38]

    Alan Tucker. 1972. A structure theorem for the consecutive 1’s property. Journal of Combinatorial Theory, Series B 12, 2 (1972), 153–162. https://doi.org/10.1016/0095-8956(72)90019-6

    1972 doi

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.