On the Tractability Landscape of the Conditional Minisum Approval Voting Rule

Evangelos Markakis; Georgios Amanatidis; Georgios Papasotiropoulos; Michael Lampis

REVIEW 3 major objections 5 minor 22 references

On the Tractability Landscape of the Conditional Minisum Approval Voting Rule

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read This paper claims that finding the winner under Conditional Minisum Approval Voting is essentially as hard as brute-force search, and that only group-dichotomous ballots or bounded per-voter dependency structure make it polynomial.

desk verdict The lower bounds are solid, but the advertised dichotomy in Theorem 4 is not proven as written; the intractability half is a one-sentence reference. read the letter →

arxiv 2412.09005 v2 pith:M7PDC6VM submitted 2024-12-12 cs.GT cs.CCcs.MA

Georgios Amanatidis , Michael Lampis , Evangelos Markakis , Georgios Papasotiropoulos This is my paper · ORCID

classification cs.GTcs.CCcs.MA MSC 68Q1768Q2591B12

keywords conditionalapprovalvotingmulti-issueelectionswinnerdeterminationcomputationalcomplexitySETHexponentialtimehypothesisvertexcovernumbertreewidth

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 sets out to map exactly when the Conditional Minisum Approval Voting rule (CMS) can be computed efficiently. Voters submit conditional approval ballots over interdependent issues, and the rule selects the outcome minimizing total dissatisfaction. Under the Strong Exponential Time Hypothesis, the paper establishes that no algorithm can substantially beat the obvious exhaustive search over all $d^m$ outcomes, and under the Exponential Time Hypothesis this near-brute-force hardness persists even when each voter's preferences depend on at most one other issue ($\Delta=1$). It then identifies two restrictions that make CMS polynomial-time solvable: group-dichotomous binary ballots, in which voters approve only coherent all-zeros or all-ones configurations, and dependency graphs with bounded vertex cover number per voter when the number of voters is constant. Both restrictions are shown to be essentially tight, giving a clean tractability landscape and a practical guideline for when conditional approval voting can be used.

What carries the argument

The argument is carried by voters' dependency graphs: each voter $i$ has a directed graph $G_i$ whose edges say which issues' outcomes the voter's approval on an issue depends on, and $\Delta$ is the maximum in-degree across voters. The brute-force benchmark is the $O(d^m)$ algorithm that tries every outcome. For hardness, three reductions do the work: k-SAT clauses encoded as conditional ballot statements (SETH lower bound), k-multicolored clique encoded as a star dependency graph (ETH lower bound at $\Delta=2$), and 2-CSP encoded as out-star dependencies (ETH lower bound at $\Delta=1$). For tractability, the group-dichotomous restriction turns each conditional ballot into a constraint that is a disjunction of one positive conjunction and one negative conjunction, a class reducible to min-cut; and the vertex cover number of a voter's graph (the size of the smallest set of issues touching every declared dependency), when bounded per voter and with constantly many voters, lets the proof augment a tree decomposition of one voter's graph by another voter's vertex cover to obtain bounded treewidth of the global dependency graph, unlocking the known polynomial algorithm.

What would settle it

To test the dichotomy, write out the reduction promised in Theorem 4: if any non-group-dichotomous conditional-approval instance with $\Delta=1$ maps to a min-CSP instance whose constraints are all two-term DNF formulas, the claimed NP-hardness is false; likewise, in Theorem 3, verify that every constraint-issue domain $D_{uv}$ contains only satisfying assignments of the corresponding 2-CSP constraint, since otherwise the reverse direction of the reduction breaks.

Watch

Extended reading notes

Core claim

The central discovery is a computational dichotomy for CMS: worst cases are essentially brute-force hard, and two natural restrictions are the polynomial-time islands. On the negative side, for every $\epsilon>0$ an algorithm running in time $d^{(1-\epsilon)m}\cdot|P|^{O(1)}$ would falsify SETH; under ETH, no $f(m)d^{o(m)}$ algorithm exists even when $\Delta=2$ and every conditional dependency graph is an in-star, and no $d^{o(m/\log m)}$ algorithm exists even when $\Delta=1$ and every conditional dependency graph is an out-star. On the positive side, for binary issues the group-dichotomous restriction—voters approve only all-zeros or all-ones configurations—reduces CMS to a minimum-constraint-satisfaction instance whose constraints are each a disjunction of one positive conjunction and one negative conjunction, a class solvable in polynomial time via min-cut; the paper claims that without this restriction the problem is NP-hard even at $\Delta=1$. In the structural direction, when $\Delta=1$ and the number of voters is constant, bounded vertex cover number in each voter's dependency graph forces bounded treewidth of the global dependency graph, so the known bounded-treewidth algorithm applies; this is tight because bounded pathwidth per voter does not suffice.

Load-bearing premise

The dichotomy of Theorem 4 rests on an unstated transfer: the hardness half assumes that every hard min-CSP constraint that is not a two-term DNF can be encoded as a conditional-approval instance that is not group-dichotomous at $\Delta=1$, but the paper asserts this in one sentence and gives no reduction.

Editorial extensions

If this is right

Under SETH, any exact algorithm for CMS must have running time $d^{\Omega(m)}$ in the worst case, so an election run under the rule should either have few issues or explicitly impose one of the tractable restrictions.
The ETH lower bounds imply that restricting each voter's conditional preferences to a single dependency (in-stars or out-stars on three issues) does not make the problem easy, so simple syntactic limits on ballot complexity cannot rescue the rule.
Group-dichotomous binary instances are polynomial-time solvable through min-cut, which means voters who express package-style preferences (all of these together or none) can be aggregated efficiently.
With a constant number of voters and $\Delta=1$, bounded vertex cover number per voter yields polynomial-time winner determination, covering natural profiles where each voter names a few critical issues that influence many others.
Both positive results are tight: removing group-dichotomy brings back NP-hardness, and allowing a nonconstant number of voters makes the vertex-cover restriction insufficient.

Reading between the lines

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

A testable extension: on real participatory-budgeting or committee ballots, one can measure what fraction of conditional approvals are group-dichotomous; if that fraction is high, the min-cut algorithm becomes a practical solver, a question the paper does not itself test.
The SETH and ETH lower bounds target exact winner determination only; they leave open whether approximating the minimum total dissatisfaction within a constant factor is easier, which would be a natural next step.
The proof of the vertex-cover result only needs the per-voter graphs to combine into bounded treewidth, so the same argument should work for any per-voter structural parameter that implies bounded vertex cover or bounded treewidth, a generalization the paper does not state.
Because both positive restrictions can be checked locally on individual ballots, the results give election organizers a practical pre-vote test: enforce group-dichotomy or bound each voter's declared dependencies before the election, and the winner can be computed in polynomial time.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Read the Amanatidis et al. paper on conditional minisum approval. The headline is that the paper overclaims: Theorem 4, the “group-dichotomous iff poly-time” boundary, is not established. The 'otherwise NP-hard' direction is one sentence: "By following the reduction proving hardness from [MP21]..." No reduction is given, and the logic is circular — it assumes the thing you'd need to prove to transfer the [KSTW01] classification. Also, as written, "if the instance is group-dichotomous then cms can be optimally solved, otherwise it is NP-hard" is not a meaningful per-instance dichotomy; NP-hardness is a property of a class. The stress-test note is right that this is load-bearing, because the paper's contribution is advertised as a complete mapping of the tractability boundary.

But there is real content here. The SETH lower bound (Theorem 1) is tight: it shows the brute-force d^m algorithm is essentially optimal. The ETH lower bounds for Delta=2 with in-stars (Theorem 2) and Delta=1 with out-stars (Theorem 3) are genuinely strong and improve on the earlier treewidth-based bound. Theorem 6, the per-voter vertex cover bound for constant voters, is a clean structural result and a nice observation that bounded per-voter pathwidth doesn't imply bounded global treewidth. Those parts check out.

Minor soft spots: Theorem 3's proof defines the domain of constraint issues as "all |Sigma|^2 possible outcomes" but the reverse direction requires the domain to be exactly the satisfying assignments of the constraint; otherwise the voter construction doesn't enforce consistency. This is fixable with a clarification. Also, the tractability half of Theorem 4 doesn't spell out how multi-statement ballots map to min-csp constraints with the same dissatisfaction count; the constraint set may need more than one constraint per voter-issue pair.

The paper is worth serious refereeing. The lower bounds alone justify it. I'd recommend conditional acceptance: require the authors to either turn the Theorem 4 intractability direction into an explicit reduction or restate the claim as "the unrestricted class is NP-hard" (already known from [BL16]) and drop the dichotomy language. The ambiguity in Theorem 3 should be clarified. If they fix these, the paper is a solid contribution to the tractability literature for this voting rule.

I'd bring it to the reading group — the Theorem 4 gap is a useful case study in how hard it is to prove a dichotomy.

Referee Report

3 major / 5 minor

Summary. The paper studies the computational complexity of the Conditional Minisum Approval (cms) rule in multi-issue elections. The first part establishes lower bounds: Theorem 1 gives a SETH-based result showing that no algorithm can solve cms in time d^{(1-epsilon)m} times a polynomial in the input size, matching the trivial brute-force d^m bound up to a subexponential factor; Theorem 2 gives an ETH lower bound of the form f(m)d^{o(m)} for instances with maximum in-degree Delta=2; Theorem 3 gives an ETH lower bound of the form d^{o(m/log m)} for Delta=1 instances. The second part proposes two tractable restrictions: Theorem 4 claims that on binary issues, cms is polynomial-time solvable when all ballots are group-dichotomous and NP-hard otherwise, even for Delta=1; Theorem 6 shows that when the number of voters is constant, Delta=1, and each voter's dependency graph has bounded vertex cover number, the global dependency graph has bounded treewidth, so cms is polynomial-time solvable. The paper also discusses the tightness of these restrictions.

Significance. If the results are correct, the paper provides a valuable and fairly complete tractability map for a central rule in conditional approval voting. The lower bounds are significant: Theorem 1 is a strong SETH-based optimality result for the brute-force algorithm, and Theorems 2 and 3 show that hardness persists even under very simple ballot structures such as in-stars and out-stars on three vertices. Theorem 6 is a clean positive result: it identifies a local, easily checkable restriction on each voter's dependency graph that implies the bounded-treewidth condition needed for the existing algorithm of Markakis and Papasotiropoulos. The proofs of Theorems 2 and 6 are transparent and appear correct, and the paper gives explicit reductions from k-multicolored clique and 2-CSP. The main weakness is Theorem 4: the hardness direction of the claimed dichotomy is not proven by the argument in the text, and the theorem's statement is ambiguous as a per-instance dichotomy. The paper's advertised contribution of exactly mapping the tractability boundary depends on this theorem, so the gap is load-bearing.

major comments (3)

[Section 4.1, Theorem 4] The hardness half of Theorem 4 is not established. NP-hardness is a property of a class of instances, not of a single non-group-dichotomous instance, so the statement 'otherwise it is NP-hard' is ill-posed if read per instance. The proof's one-sentence appeal to [MP21] and [KSTW01]—'By following the reduction proving hardness from [MP21]...'—does not supply a reduction, does not verify that the produced cms instances satisfy Delta=1, and does not show that they are non-group-dichotomous. The reference to [KSTW01] also does not justify the claim, because that paper's classification applies to constraint languages, not to the particular DNF form described earlier. The conclusion may be recoverable by citing the existing NP-hardness of cms from [BL16] and observing that those hard Delta=1 instances are not group-dichotomous, but that argument is not made and the current proof is not a valid derivation. This is a load-bearing point because the paper advertises Theorem 4 as exactly locating the tractability boundary.
[Section 3, Theorem 3] The construction of the constraint issues I_{uv} is ambiguous and, under the literal reading, the reverse direction of the reduction fails. The text says that D_{uv} is 'a list of all the |Sigma|^2 possible outcomes of the corresponding constraint,' but the reverse direction relies on the outcome of I_{uv} being a satisfying assignment of that constraint. If D_{uv} contains all |Sigma|^2 pairs, then an outcome that selects a non-satisfying pair for I_{uv} will satisfy every voter regardless of the values of I_u and I_v, because no voter was added for that pair; the extracted assignment may then violate the constraint while total dissatisfaction is zero. The proof should restrict D_{uv} to the set of satisfying assignments of the constraint, and it should also address constraints with no satisfying assignments.
[Section 4.1, tractability proof of Theorem 4] The encoding of the case where a voter approves both 0_j and 1_j for issue I_j is unclear and appears to contain a simplification error. As printed, the constraint (x_j ∧ ∧_k y_k) ∨ (\bar{x}_j ∧ ∧_k \bar{y}_k) is not equivalent to ∧_k y_k; the displayed formula therefore does not support the claimed reduction to min-cut. The proof also does not state how multiple conditional statements for the same issue are aggregated into constraints, which matters because a group-dichotomous ballot may contain more than one statement for a single issue. Please restate this part of the reduction explicitly and verify the equivalence for each allowed statement type.

minor comments (5)

[Section 3, after Theorem 3] The paragraph discussing structural graph parameters says the hardness proofs are 'as strong as they could be' because the number of vertices in the global dependency graph equals m and upper-bounds pathwidth and vertex cover number; this is correct but should be stated more carefully, since the upper bound by m is trivial and does not by itself imply optimality of the running-time exponents.
[Section 4.2, Observation 2] The proof says the pathwidth of the voters' dependency graphs equals 1; for a disjoint union of paths the pathwidth is at most 1, and saying 'equals 1' is harmless for nonempty paths, but the wording could be tightened.
[Section 4.2, Theorem 6] The proof of bounded treewidth for the global dependency graph is correct but terse: it should explicitly say that every edge of the first voter's graph has at least one endpoint in the vertex cover C, so adding C to every bag of the tree decomposition of the second voter's graph yields a valid tree decomposition of the union. This would help readers who are not experts in treewidth.
[Section 1 and abstract] There are duplicated passages and typographical artifacts in the introduction (for example, a paragraph beginning 'This work examines the feasibility of conditional approval voting...' repeats the contribution summary), and several OCR-style misspellings such as 'V oting' and 'di fferent' appear throughout the text.
[Section 5, Conclusions] The concluding sentence states that the paper 'effectively and completely resolves the question of efficient computation' of cms; given the gaps in Theorem 4, this claim is too strong as written and should be moderated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the SETH/ETH lower bounds are self-contained reductions, and the [MP21] treewidth dichotomy is a legitimate prior-work dependency, not a self-referential derivation.

full rationale

The derivation chain is largely self-contained. Theorem 1 reduces k-SAT to cms with an explicit ballot construction and proves both directions; Theorem 2 is an explicit reduction from multicolored clique; Theorem 3 is an explicit reduction from 2-CSP. None of these define cms in terms of its own output or fit parameters to the quantity being predicted. The positive direction of Theorem 4 gives an explicit polynomial-time reduction of group-dichotomous cms to min-csp with two-term DNF constraints and then cites [KS96] for the min-cut algorithm; this is independent of the present paper's own conclusions. Theorem 6 is a structural graph argument showing bounded vertex cover per voter plus constantly many voters yields bounded treewidth of the global dependency graph, and it then invokes Theorem 5 of [MP21] as a black box; that cited theorem is a published result by two of the same authors, but its statement does not assume the present theorems, and it is parameter-free with stated assumptions (FPT != W[1], Delta = 1, recursively enumerable graph class). The reliance is a normal dependency on prior work, not a definitional equivalence. The one genuine weakness, flagged for correctness rather than circularity, is the intractability half of Theorem 4: it is asserted via a one-sentence reference to the reduction of [MP21] and the classification of [KSTW01] without an explicit construction verifying that the produced cms instances are non-group-dichotomous. That is a proof gap, not a circular step, because no quantity in the paper is defined in terms of itself and no fitted input is relabeled as a prediction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No numeric parameters are fitted to data; the paper is a purely combinatorial complexity analysis. The axioms listed are the complexity conjectures (SETH, ETH), the external Min-CSP classification, the black-box use of the [MP21] treewidth theorem, and two unproven structural properties assumed inside Theorem 4 and Theorem 3. No new physical or mathematical entities are postulated; all gadgets are standard voters, issues, and auxiliary min-cut nodes.

assumptions (6)

domain assumption Strong Exponential Time Hypothesis (SETH)
Invoked in Theorem 1 (Section 3) to prove the d^((1-epsilon)m) lower bound; a standard complexity conjecture, not proved in the paper.
domain assumption Exponential Time Hypothesis (ETH)
Invoked in Theorems 2 and 3 (Section 3) through the multicolored clique lower bound of [CHKX06] and the 2-CSP lower bound of [Mar10]/[KMPS24]; standard conjecture.
domain assumption Theorem 5 of [MP21]: bounded global treewidth with Delta=1 implies polynomial-time cms
Used as a black box in Theorem 6 (Section 4.2); a published result co-authored by two of the present authors. Also provides the treewidth dichotomy under FPT != W[1].
standard math KSTW01 Min-CSP classification
Theorem 4's hardness argument relies on the classification that Min-CSP is NP-hard for constraint relations beyond the 2-monotone DNF class (Section 4.1). Standard external theorem.
ad hoc to paper Transfer property of the [MP21] hardness reduction for non-group-dichotomous ballots
The proof of Theorem 4's 'otherwise NP-hard' direction asserts, without demonstration, that the [MP21] reduction can encode arbitrary hard non-2-monotone Min-CSP relations using non-group-dichotomous ballots (Section 4.1, final paragraph of the proof of Theorem 4).
ad hoc to paper Constraint-issue domains consist of satisfying assignments in Theorem 3
The 2-CSP reduction requires D_uv to be the set of satisfying pairs of the constraint; the text says 'all the |Sigma|^2 possible outcomes', and the reverse direction fails under the literal reading (Section 3, Theorem 3 proof).

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Tractability Landscape of the Conditional Minisum Approval Voting Rule." pith.science (2026). https://pith.science/paper/M7PDC6VM

@misc{pith2026241209005,
  author       = {Pith},
  title        = {Pith review of: On the Tractability Landscape of the Conditional Minisum Approval Voting Rule},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M7PDC6VM}},
  note         = {Machine review of arXiv:2412.09005}
}

read the original abstract

This work examines the Conditional Approval Framework for elections involving multiple interdependent issues, specifically focusing on the Conditional Minisum Approval Voting Rule. We first conduct a detailed analysis of the computational complexity of this rule, demonstrating that no approach can significantly outperform the brute-force algorithm under common computational complexity assumptions and various natural input restrictions. In response, we propose two practical restrictions (the first in the literature) that make the problem computationally tractable and show that these restrictions are essentially tight. Overall, this work provides a clear picture of the tractability landscape of the problem, contributing to a comprehensive understanding of the complications introduced by conditional ballots and indicating that conditional approval voting can be applied in practice, albeit under specific conditions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in ":" * " " * FUNCTION f...
[2]

Conditional and sequential approval voting on combinatorial domains

Nathana \" e l Barrot and J \' e r \^ o me Lang. Conditional and sequential approval voting on combinatorial domains. In International Joint Conference on Artificial Intelligence , pages 88--94, 2016

work page 2016
[3]

Proportionality guarantees in elections with interdependent issues

Markus Brill, Evangelos Markakis, Georgios Papasotiropoulos, and Jannik Peters. Proportionality guarantees in elections with interdependent issues. In International Joint Conference on Artificial Intelligence , pages 2537--2545, 2023

work page 2023
[4]

Parameterized algorithms

Marek Cygan, Fedor Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized algorithms . Springer, 2015

work page 2015
[5]

Strong computational lower bounds via parameterized complexity

Jianer Chen, Xiuzhen Huang, Iyad A Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences , 72(8):1346--1367, 2006

work page 2006
[6]

A structural approach to activity selection

Eduard Eiben, Robert Ganian, and Sebastian Ordyniak. A structural approach to activity selection. In International Joint Conference on Artificial Intelligence , pages 203--209, 2018

work page 2018
[7]

Parameterized complexity of coloring problems: T reewidth versus vertex cover

Ji r \' Fiala, Petr Golovach, and Jan Kratochv \' l. Parameterized complexity of coloring problems: T reewidth versus vertex cover. Theoretical Computer Science , 412(23):2513--2523, 2011

work page 2011
[8]

Graph layout problems parameterized by vertex cover

Michael Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances Rosamond, and Saket Saurabh. Graph layout problems parameterized by vertex cover. In Algorithms and Computation: International Symposium , pages 294--305, 2008

work page 2008

Show all 22 references

[9]

The complexity ecology of parameters: A n illustration using bounded max leaf number

Michael Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances Rosamond, and Saket Saurabh. The complexity ecology of parameters: A n illustration using bounded max leaf number. Theory of Computing Systems , 45:822--848, 2009

2009
[10]

On the complexity of k- SAT

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k- SAT . Journal of Computer and System Sciences , 62(2):367--375, 2001

2001
[11]

Phragm \'e n's and T hiele's election methods

Svante Janson. Phragm \'e n's and T hiele's election methods. Technical report, arXiv:1611.08826 [math.HO], 2016

2016 arXiv
[12]

Karthik C. S. , D \' a niel Marx, Marcin Pilipczuk, and U \' e verton Souza. Conditional lower bounds for sparse parameterized 2- CSP : A streamlined proof. In Symposium on Simplicity in Algorithms , pages 383--395, 2024

2024
[13]

The optimization complexity of constraint satisfaction problems

Sanjeev Khanna and Madhu Sudan. The optimization complexity of constraint satisfaction problems. In Electonic Colloquium on Computational Complexity , 1996

1996
[14]

The approximability of constraint satisfaction problems

Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David Williamson. The approximability of constraint satisfaction problems. SIAM Journal on Computing , 30(6):1863--1920, 2001

1920
[15]

Algorithmic meta-theorems for restrictions of treewidth

Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica , 64:19--37, 2012

2012
[16]

Voting in combinatorial domains

J \' e r \^ o me Lang and Lirong Xia. Voting in combinatorial domains. In Handbook of Computational Social Choice , pages 197--222. Cambridge University Press, 2016

2016
[17]

Can you beat treewidth? Theory of Computing , 6(1):85--112, 2010

D \' a niel Marx. Can you beat treewidth? Theory of Computing , 6(1):85--112, 2010

2010
[18]

Computational aspects of conditional minisum approval voting in elections with interdependent issues

Evangelos Markakis and Georgios Papasotiropoulos. Computational aspects of conditional minisum approval voting in elections with interdependent issues. In International Joint Conference on Artificial Intelligence , pages 304--310, 2020

2020
[19]

Winner determination and strategic control in conditional approval voting

Evangelos Markakis and Georgios Papasotiropoulos. Winner determination and strategic control in conditional approval voting. In International Joint Conference on Artificial Intelligence , pages 342--348, 2021

2021
[20]

Proportionality and the limits of welfarism

Dominik Peters and Piotr Skowron. Proportionality and the limits of welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation , pages 793--794, 2020

2020
[21]

Graph minors

Neil Robertson and Paul Seymour. Graph minors. II . A lgorithmic aspects of tree-width. Journal of algorithms , 7(3):309--322, 1986

1986
[22]

Om flerfoldsvalg

Thorvald Nicolai Thiele. Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger , pages 415--441, 1895

Pith tools

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

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in ":" * " " * FUNCTION f...

[2] [2]

Conditional and sequential approval voting on combinatorial domains

Nathana \" e l Barrot and J \' e r \^ o me Lang. Conditional and sequential approval voting on combinatorial domains. In International Joint Conference on Artificial Intelligence , pages 88--94, 2016

work page 2016

[3] [3]

Proportionality guarantees in elections with interdependent issues

Markus Brill, Evangelos Markakis, Georgios Papasotiropoulos, and Jannik Peters. Proportionality guarantees in elections with interdependent issues. In International Joint Conference on Artificial Intelligence , pages 2537--2545, 2023

work page 2023

[4] [4]

Parameterized algorithms

Marek Cygan, Fedor Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized algorithms . Springer, 2015

work page 2015

[5] [5]

Strong computational lower bounds via parameterized complexity

Jianer Chen, Xiuzhen Huang, Iyad A Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences , 72(8):1346--1367, 2006

work page 2006

[6] [6]

A structural approach to activity selection

Eduard Eiben, Robert Ganian, and Sebastian Ordyniak. A structural approach to activity selection. In International Joint Conference on Artificial Intelligence , pages 203--209, 2018

work page 2018

[7] [7]

Parameterized complexity of coloring problems: T reewidth versus vertex cover

Ji r \' Fiala, Petr Golovach, and Jan Kratochv \' l. Parameterized complexity of coloring problems: T reewidth versus vertex cover. Theoretical Computer Science , 412(23):2513--2523, 2011

work page 2011

[8] [8]

Graph layout problems parameterized by vertex cover

Michael Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances Rosamond, and Saket Saurabh. Graph layout problems parameterized by vertex cover. In Algorithms and Computation: International Symposium , pages 294--305, 2008

work page 2008