references.bib

@inproceedings{bouchez2006,
  author    = {Florent Bouchez and Alain Darte and Christophe Guillon and Fabrice Rastello},
  title     = {Register Allocation: What Does the {NP}-Completeness Proof of {Chaitin} et al. Really Prove?},
  booktitle = {Languages and Compilers for Parallel Computing (LCPC)},
  series    = {LNCS},
  volume    = {4382},
  pages     = {283--298},
  year      = {2006},
  publisher = {Springer},
  doi       = {10.1007/978-3-540-72521-3_21}
}

@inproceedings{ahoJohnsonUllman1977,
  author    = {Alfred V. Aho and Steven C. Johnson and Jeffrey D. Ullman},
  title     = {Code Generation for Machines with Multiregister Operations},
  booktitle = {Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages},
  pages     = {21--28},
  year      = {1977},
  publisher = {ACM},
  doi       = {10.1145/512950.512953}
}

@article{brunoSethi1976,
  author  = {John Bruno and Ravi Sethi},
  title   = {Code Generation for a One-Register Machine},
  journal = {Journal of the ACM},
  volume  = {23},
  number  = {3},
  pages   = {502--510},
  year    = {1976},
  doi     = {10.1145/321958.321974}
}

@article{sethi1975,
  author  = {Ravi Sethi},
  title   = {Complete Register Allocation Problems},
  journal = {SIAM Journal on Computing},
  volume  = {4},
  number  = {3},
  pages   = {226--248},
  year    = {1975},
  doi     = {10.1137/0204020}
}

@article{sethiUllman1970,
  author  = {Ravi Sethi and Jeffrey D. Ullman},
  title   = {The Generation of Optimal Code for Arithmetic Expressions},
  journal = {Journal of the ACM},
  volume  = {17},
  number  = {4},
  pages   = {715--728},
  year    = {1970},
  doi     = {10.1145/321607.321620}
}

@phdthesis{kessler1998,
  author  = {Christoph W. Kessler},
  title   = {Scheduling Expression {DAG}s for Minimal Register Need},
  school  = {Universit{\"a}t des Saarlandes},
  year    = {1998}
}

@inproceedings{wagner1975,
  author    = {Robert A. Wagner},
  title     = {On the Complexity of the Extended String-to-String Correction Problem},
  booktitle = {Proceedings of the 7th Annual ACM Symposium on Theory of Computing (STOC)},
  pages     = {218--223},
  year      = {1975},
  doi       = {10.1145/800116.803771}
}

@article{wagner1974,
  author  = {Robert A. Wagner and Michael J. Fischer},
  title   = {The String-to-String Correction Problem},
  journal = {Journal of the ACM},
  volume  = {21},
  number  = {1},
  pages   = {168--173},
  year    = {1974},
  doi     = {10.1145/321796.321811}
}

@article{juttner2018,
  author  = {Alpár Jüttner and Péter Madarasi},
  title   = {VF2++ — An improved subgraph isomorphism algorithm},
  journal = {Discrete Applied Mathematics},
  volume  = {242},
  pages   = {69--81},
  year    = {2018},
  doi     = {10.1016/j.dam.2018.02.018}
}

@article{moore1968,
  author  = {J. Michael Moore},
  title   = {An $n$ Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs},
  journal = {Management Science},
  volume  = {15},
  number  = {1},
  pages   = {102--109},
  year    = {1968},
  doi     = {10.1287/mnsc.15.1.102}
}

@article{lawler1978,
  author  = {Eugene L. Lawler},
  title   = {Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints},
  journal = {Annals of Discrete Mathematics},
  volume  = {2},
  pages   = {75--90},
  year    = {1978},
  doi     = {10.1016/S0167-5060(08)70356-7}
}

@article{smith1956,
  author  = {W. E. Smith},
  title   = {Various Optimizers for Single-Stage Production},
  journal = {Naval Research Logistics Quarterly},
  volume  = {3},
  number  = {1--2},
  pages   = {59--66},
  year    = {1956},
  doi     = {10.1002/nav.3800030106}
}

@article{johnson1954,
  author  = {Selmer M. Johnson},
  title   = {Optimal two- and three-stage production schedules with setup times included},
  journal = {Naval Research Logistics Quarterly},
  volume  = {1},
  number  = {1},
  pages   = {61--68},
  year    = {1954},
  doi     = {10.1002/nav.3800010110}
}

@article{shang2018,
  author  = {Lei Shang and Chao Wan and Jianan Wang},
  title   = {An exact algorithm for the three-machine flow shop problem},
  journal = {Computers \& Operations Research},
  volume  = {91},
  pages   = {79--89},
  year    = {2018},
  doi     = {10.1016/j.cor.2017.10.015}
}

@article{bartholdi1980,
  author  = {John J. Bartholdi and James B. Orlin and H. Donald Ratliff},
  title   = {Cyclic Scheduling via Integer Programs with Circular Ones},
  journal = {Operations Research},
  volume  = {28},
  number  = {5},
  pages   = {1074--1085},
  year    = {1980},
  doi     = {10.1287/opre.28.5.1074}
}

@article{brucker1977,
  author  = {Peter Brucker and Jan Karel Lenstra and Alexander H. G. Rinnooy Kan},
  title   = {Complexity of Machine Scheduling Problems},
  journal = {Annals of Discrete Mathematics},
  volume  = {1},
  pages   = {343--362},
  year    = {1977},
  doi     = {10.1016/S0167-5060(08)70743-X}
}

@incollection{brucker1978clustering,
  author    = {Peter Brucker},
  title     = {On the Complexity of Clustering Problems},
  booktitle = {Optimization and Operations Research},
  series    = {Lecture Notes in Economics and Mathematical Systems},
  volume    = {157},
  pages     = {45--54},
  publisher = {Springer},
  year      = {1978}
}

@article{lawler1977,
  author  = {Eugene L. Lawler},
  title   = {A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness},
  journal = {Annals of Discrete Mathematics},
  volume  = {1},
  pages   = {331--342},
  year    = {1977},
  doi     = {10.1016/S0167-5060(08)70742-8}
}

@article{potts1985,
  author  = {Chris N. Potts and Luk N. Van Wassenhove},
  title   = {A Branch and Bound Algorithm for the Total Weighted Tardiness Problem},
  journal = {Operations Research},
  volume  = {33},
  number  = {2},
  pages   = {363--377},
  year    = {1985},
  doi     = {10.1287/opre.33.2.363}
}

@article{tanaka2009,
  author  = {Shunji Tanaka and Shuji Fujikuma and Mituhiko Araki},
  title   = {An exact algorithm for single-machine scheduling without machine idle time},
  journal = {Journal of Scheduling},
  volume  = {12},
  number  = {6},
  pages   = {575--593},
  year    = {2009},
  doi     = {10.1007/s10951-008-0093-5}
}

@inproceedings{karp1972,
  author    = {Richard M. Karp},
  title     = {Reducibility among Combinatorial Problems},
  booktitle = {Complexity of Computer Computations},
  publisher = {Plenum Press},
  year      = {1972},
  pages     = {85--103}
}

@article{lagarias1985,
  author  = {Jeffrey C. Lagarias and Andrew M. Odlyzko},
  title   = {Solving Low-Density Subset Sum Problems},
  journal = {Journal of the ACM},
  volume  = {32},
  number  = {1},
  pages   = {229--246},
  year    = {1985},
  doi     = {10.1145/2455.2461}
}

@article{coster1992,
  author  = {Matthijs J. Coster and Antoine Joux and Brian A. LaMacchia and Andrew M. Odlyzko and Claus-Peter Schnorr and Jacques Stern},
  title   = {Improved Low-Density Subset Sum Algorithms},
  journal = {Computational Complexity},
  volume  = {2},
  number  = {2},
  pages   = {111--128},
  year    = {1992},
  doi     = {10.1007/BF01201999}
}

@inproceedings{cook1971,
  author    = {Stephen A. Cook},
  title     = {The Complexity of Theorem-Proving Procedures},
  booktitle = {Proceedings of the Third Annual ACM Symposium on Theory of Computing},
  year      = {1971},
  pages     = {151--158}
}

@book{garey1979,
  author    = {Michael R. Garey and David S. Johnson},
  title     = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
  publisher = {W. H. Freeman},
  year      = {1979}
}

@article{orlin1977,
  author  = {James B. Orlin},
  title   = {Contentment in Graph Theory: Covering Graphs with Cliques},
  journal = {Indagationes Mathematicae (Proceedings)},
  volume  = {80},
  number  = {5},
  pages   = {406--424},
  year    = {1977},
  doi     = {10.1016/1385-7258(77)90055-5}
}

@article{kouStockmeyerWong1978,
  author  = {Lawrence T. Kou and Larry J. Stockmeyer and C. K. Wong},
  title   = {Covering Edges by Cliques with Regard to Keyword Conflicts and Intersection Graphs},
  journal = {Communications of the ACM},
  volume  = {21},
  number  = {2},
  pages   = {135--139},
  year    = {1978},
  doi     = {10.1145/359340.359346}
}

@article{galilMegiddo1977,
  author  = {Zvi Galil and Nimrod Megiddo},
  title   = {Cyclic Ordering is NP-Complete},
  journal = {Theoretical Computer Science},
  volume  = {5},
  number  = {2},
  pages   = {179--182},
  year    = {1977},
  doi     = {10.1016/0304-3975(77)90005-1}
}

@article{florianLenstraRinnooyKan1980,
  author  = {M. Florian and J. K. Lenstra and A. H. G. Rinnooy Kan},
  title   = {Deterministic Production Planning: Algorithms and Complexity},
  journal = {Management Science},
  volume  = {26},
  number  = {7},
  pages   = {669--679},
  year    = {1980}
}

@article{busingstiller2011,
  author  = {Christina Büsing and Sebastian Stiller},
  title   = {Line planning, path constrained network flow and inapproximability},
  journal = {Networks},
  volume  = {57},
  number  = {1},
  pages   = {106--113},
  year    = {2011},
  doi     = {10.1002/net.20386}
}

@article{kawarabayashiKobayashiReed2012,
  author  = {Ken-ichi Kawarabayashi and Yusuke Kobayashi and Bruce Reed},
  title   = {The disjoint paths problem in quadratic time},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {102},
  number  = {2},
  pages   = {424--435},
  year    = {2012},
  doi     = {10.1016/j.jctb.2011.07.004}
}

@article{robertsonSeymour1995,
  author  = {Neil Robertson and P. D. Seymour},
  title   = {Graph Minors. XIII. The Disjoint Paths Problem},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {63},
  number  = {1},
  pages   = {65--110},
  year    = {1995},
  doi     = {10.1006/jctb.1995.1006}
}

@inproceedings{vansicklechandy1977,
  author    = {Lawrence Van Sickle and K. Mani Chandy},
  title     = {Computational Complexity of Network Design Algorithms},
  booktitle = {IFIP Congress 77},
  pages     = {235--239},
  year      = {1977}
}

@article{bruckerGareyJohnson1977,
  author  = {Peter Brucker and Michael R. Garey and David S. Johnson},
  title   = {Scheduling equal-length tasks under tree-like precedence constraints to minimize maximum lateness},
  journal = {Mathematics of Operations Research},
  volume  = {2},
  number  = {3},
  pages   = {275--284},
  year    = {1977}
}

@article{eswarantarjan1976,
  author  = {K. P. Eswaran and Robert E. Tarjan},
  title   = {Augmentation Problems},
  journal = {SIAM Journal on Computing},
  volume  = {5},
  number  = {4},
  pages   = {653--665},
  year    = {1976},
  doi     = {10.1137/0205044}
}

@article{hassin1992,
  author  = {Refael Hassin},
  title   = {Approximation Schemes for the Restricted Shortest Path Problem},
  journal = {Mathematics of Operations Research},
  volume  = {17},
  number  = {1},
  pages   = {36--42},
  year    = {1992},
  doi     = {10.1287/moor.17.1.36}
}

@article{joksch1966,
  author  = {Hans C. Joksch},
  title   = {The Shortest Route Problem with Constraints},
  journal = {Journal of Mathematical Analysis and Applications},
  volume  = {14},
  number  = {2},
  pages   = {191--197},
  year    = {1966},
  doi     = {10.1016/0022-247X(66)90002-6}
}

@article{lorenzraz2001,
  author  = {Daniel H. Lorenz and Danny Raz},
  title   = {A Simple Efficient Approximation Scheme for the Restricted Shortest Path Problem},
  journal = {Operations Research Letters},
  volume  = {28},
  number  = {5},
  pages   = {213--219},
  year    = {2001},
  doi     = {10.1016/S0167-6377(01)00079-6}
}

@article{gareyJohnsonStockmeyer1976,
  author  = {Michael R. Garey and David S. Johnson and Larry Stockmeyer},
  title   = {Some Simplified {NP}-Complete Graph Problems},
  journal = {Theoretical Computer Science},
  volume  = {1},
  number  = {3},
  pages   = {237--267},
  year    = {1976}
}

@inproceedings{gavril1977,
  author    = {F. Gavril},
  title     = {Some {NP}-Complete Problems on Graphs},
  booktitle = {Proceedings of the 11th Conference on Information Sciences and Systems},
  pages     = {91--95},
  year      = {1977}
}

@article{evenItaiShamir1976,
  author  = {Shimon Even and Alon Itai and Adi Shamir},
  title   = {On the Complexity of Timetable and Multicommodity Flow Problems},
  journal = {SIAM Journal on Computing},
  volume  = {5},
  number  = {4},
  pages   = {691--703},
  year    = {1976},
  doi     = {10.1137/0205048}
}

@article{itai1978,
  author  = {Alon Itai},
  title   = {Two-Commodity Flow},
  journal = {Journal of the ACM},
  volume  = {25},
  number  = {4},
  pages   = {596--611},
  year    = {1978},
  doi     = {10.1137/0203021}
}

@article{jewell1962,
  author  = {William S. Jewell},
  title   = {Optimal Flow Through Networks with Gains},
  journal = {Operations Research},
  volume  = {10},
  number  = {4},
  pages   = {476--499},
  year    = {1962},
  doi     = {10.1287/opre.10.4.476}
}

@article{sahni1974,
  author  = {Sartaj Sahni},
  title   = {Computationally Related Problems},
  journal = {SIAM Journal on Computing},
  volume  = {3},
  number  = {4},
  pages   = {262--279},
  year    = {1974}
}

@article{abdelWahabKameda1978,
  author  = {H. M. Abdel-Wahab and T. Kameda},
  title   = {Scheduling to Minimize Maximum Cumulative Cost Subject to Series-Parallel Precedence Constraints},
  journal = {Operations Research},
  volume  = {26},
  number  = {1},
  pages   = {141--158},
  year    = {1978},
  doi     = {10.1287/opre.26.1.141}
}

@article{monmaSidney1979,
  author  = {Clyde L. Monma and Jeffrey B. Sidney},
  title   = {Sequencing with Series-Parallel Precedence Constraints},
  journal = {Mathematics of Operations Research},
  volume  = {4},
  number  = {3},
  pages   = {215--224},
  year    = {1979},
  doi     = {10.1287/moor.4.3.215}
}

@article{evenTarjan1976,
  author  = {Shimon Even and Robert Endre Tarjan},
  title   = {A Combinatorial Problem Which Is Complete in Polynomial Space},
  journal = {Journal of the ACM},
  volume  = {23},
  number  = {4},
  pages   = {710--719},
  year    = {1976}
}

@article{brunoWeinberg1970,
  author  = {John Bruno and Louis Weinberg},
  title   = {A Constructive Graph-Theoretic Solution of the Shannon Switching Game},
  journal = {IEEE Transactions on Circuit Theory},
  volume  = {17},
  number  = {1},
  pages   = {74--81},
  year    = {1970}
}

@article{glover2019,
  author  = {Fred Glover and Gary Kochenberger and Yu Du},
  title   = {Quantum Bridge Analytics {I}: a tutorial on formulating and using {QUBO} models},
  journal = {4OR},
  volume  = {17},
  pages   = {335--371},
  year    = {2019},
  doi     = {10.1007/s10288-019-00424-y}
}

@article{lucas2014,
  author  = {Andrew Lucas},
  title   = {Ising formulations of many NP problems},
  journal = {Frontiers in Physics},
  volume  = {2},
  number  = {5},
  year    = {2014}
}

@article{beeri1979,
  author  = {Catriel Beeri and Philip A. Bernstein},
  title   = {Computational Problems Related to the Design of Normal Form Relational Schemas},
  journal = {ACM Transactions on Database Systems},
  volume  = {4},
  number  = {1},
  pages   = {30--59},
  year    = {1979},
  doi     = {10.1145/320064.320066}
}

@article{barahona1982,
  author  = {Francisco Barahona},
  title   = {On the computational complexity of Ising spin glass models},
  journal = {Journal of Physics A: Mathematical and General},
  volume  = {15},
  number  = {10},
  pages   = {3241--3253},
  year    = {1982}
}

@article{edmonds1965,
  author  = {Jack Edmonds},
  title   = {Paths, Trees, and Flowers},
  journal = {Canadian Journal of Mathematics},
  volume  = {17},
  pages   = {449--467},
  year    = {1965}
}

@article{whitfield2012,
  author  = {James D. Whitfield and Mauro Faccin and Jacob D. Biamonte},
  title   = {Ground-state spin logic},
  journal = {EPL (Europhysics Letters)},
  volume  = {99},
  number  = {5},
  pages   = {57004},
  year    = {2012}
}

@article{nguyen2023,
  author  = {Minh-Thi Nguyen and Jin-Guo Liu and Jonathan Wurtz and Mikhail D. Lukin and Sheng-Tao Wang and Hannes Pichler},
  title   = {Quantum Optimization with Arbitrary Connectivity Using {R}ydberg Atom Arrays},
  journal = {PRX Quantum},
  volume  = {4},
  pages   = {010316},
  year    = {2023},
  doi     = {10.1103/PRXQuantum.4.010316}
}

@article{xiao2017,
  author  = {Mingyu Xiao and Hiroshi Nagamochi},
  title   = {Exact Algorithms for Maximum Independent Set},
  journal = {Information and Computation},
  volume  = {255},
  pages   = {126--146},
  year    = {2017},
  doi     = {10.1016/j.ic.2017.06.001}
}

@article{robson1986,
  author  = {J. M. Robson},
  title   = {Algorithms for Maximum Independent Sets},
  journal = {Journal of Algorithms},
  volume  = {7},
  number  = {3},
  pages   = {425--440},
  year    = {1986},
  doi     = {10.1016/0196-6774(86)90032-5}
}

@article{robson2001,
  author  = {J. M. Robson},
  title   = {Finding a Maximum Independent Set in Time $O(2^{n/4})$},
  year    = {2001},
  note    = {Technical Report 1251-01, LaBRI, Université Bordeaux I}
}

@article{vanrooij2013,
  author  = {Johan M. M. van Rooij and Marcel van Kooten Niekerk and Hans L. Bodlaender},
  title   = {Partition Into Triangles on Bounded Degree Graphs},
  journal = {Theory of Computing Systems},
  volume  = {52},
  number  = {4},
  pages   = {687--718},
  year    = {2013},
  doi     = {10.1007/s00224-012-9412-5}
}

@article{vanrooij2011,
  author  = {Johan M. M. van Rooij and Hans L. Bodlaender},
  title   = {Exact algorithms for dominating set},
  journal = {Discrete Applied Mathematics},
  volume  = {159},
  number  = {17},
  pages   = {2147--2164},
  year    = {2011},
  doi     = {10.1016/j.dam.2011.07.001}
}

@article{williams2005,
  author  = {Ryan Williams},
  title   = {A new algorithm for optimal 2-constraint satisfaction and its implications},
  journal = {Theoretical Computer Science},
  volume  = {348},
  number  = {2--3},
  pages   = {357--365},
  year    = {2005},
  doi     = {10.1016/j.tcs.2005.09.023}
}

@article{tomita2006,
  author  = {Etsuji Tomita and Akira Tanaka and Haruhisa Takahashi},
  title   = {The worst-case time complexity for generating all maximal cliques and computational experiments},
  journal = {Theoretical Computer Science},
  volume  = {363},
  number  = {1},
  pages   = {28--42},
  year    = {2006},
  doi     = {10.1016/j.tcs.2006.06.015}
}

@article{heldkarp1962,
  author  = {Michael Held and Richard M. Karp},
  title   = {A Dynamic Programming Approach to Sequencing Problems},
  journal = {Journal of the Society for Industrial and Applied Mathematics},
  volume  = {10},
  number  = {1},
  pages   = {196--210},
  year    = {1962},
  doi     = {10.1137/0110015}
}

@article{gilmore1964,
  author  = {P. C. Gilmore and R. E. Gomory},
  title   = {Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem},
  journal = {Operations Research},
  volume  = {12},
  number  = {5},
  pages   = {655--679},
  year    = {1964},
  doi     = {10.1287/opre.12.5.655}
}

@article{beigel2005,
  author  = {Richard Beigel and David Eppstein},
  title   = {3-Coloring in Time {$O(1.3289^n)$}},
  journal = {Journal of Algorithms},
  volume  = {54},
  number  = {2},
  pages   = {168--204},
  year    = {2005},
  doi     = {10.1016/j.jalgor.2004.06.008}
}

@inproceedings{wu2024,
  author    = {Pu Wu and Huanyu Gu and Huiqin Jiang and Zehui Shao and Jin Xu},
  title     = {A Faster Algorithm for the 4-Coloring Problem},
  booktitle = {European Symposium on Algorithms (ESA)},
  series    = {LIPIcs},
  volume    = {308},
  pages     = {103:1--103:16},
  year      = {2024},
  doi       = {10.4230/LIPIcs.ESA.2024.103}
}

@inproceedings{zamir2021,
  author    = {Or Zamir},
  title     = {Breaking the {$2^n$} Barrier for 5-Coloring and 6-Coloring},
  booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)},
  series    = {LIPIcs},
  volume    = {198},
  pages     = {113:1--113:20},
  year      = {2021},
  doi       = {10.4230/LIPIcs.ICALP.2021.113}
}

@article{bjorklund2014,
  author  = {Andreas Bj\"{o}rklund},
  title   = {Determinant Sums for Undirected {H}amiltonicity},
  journal = {SIAM Journal on Computing},
  volume  = {43},
  number  = {1},
  pages   = {280--299},
  year    = {2014},
  doi     = {10.1137/110839229}
}

@article{bjorklund2009,
  author  = {Andreas Bj\"{o}rklund and Thore Husfeldt and Mikko Koivisto},
  title   = {Set Partitioning via Inclusion-Exclusion},
  journal = {SIAM Journal on Computing},
  volume  = {39},
  number  = {2},
  pages   = {546--563},
  year    = {2009},
  doi     = {10.1137/070683933}
}

@incollection{jarvisalo2012,
  author    = {Matti J\"{a}rvisalo and Petteri Kaski and Mikko Koivisto and Janne H. Korhonen},
  title     = {Finding Efficient Circuits for Ensemble Computation},
  booktitle = {Theory and Applications of Satisfiability Testing -- SAT 2012},
  series    = {Lecture Notes in Computer Science},
  volume    = {7317},
  pages     = {369--382},
  year      = {2012},
  publisher = {Springer},
  doi       = {10.1007/978-3-642-31612-8_28}
}

@article{aspvall1979,
  author  = {Bengt Aspvall and Michael F. Plass and Robert Endre Tarjan},
  title   = {A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas},
  journal = {Information Processing Letters},
  volume  = {8},
  number  = {3},
  pages   = {121--123},
  year    = {1979},
  doi     = {10.1016/0020-0190(79)90002-4}
}

@article{lichtenstein1982,
  author  = {David Lichtenstein},
  title   = {Planar Formulae and Their Uses},
  journal = {SIAM Journal on Computing},
  volume  = {11},
  number  = {2},
  pages   = {329--343},
  year    = {1982},
  doi     = {10.1137/0211025}
}

@inproceedings{hansen2019,
  author    = {Thomas Dueholm Hansen and Haim Kaplan and Or Zamir and Uri Zwick},
  title     = {Faster $k$-{SAT} Algorithms Using Biased-{PPSZ}},
  booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)},
  pages     = {578--589},
  year      = {2019},
  doi       = {10.1145/3313276.3316359}
}

@phdthesis{dadush2012,
  author = {Daniel Dadush},
  title  = {Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation},
  school = {Georgia Institute of Technology},
  year   = {2012}
}

@incollection{lenstra1993,
  author    = {Arjen K. Lenstra and Hendrik W. Lenstra and Mark S. Manasse and John M. Pollard},
  title     = {The Number Field Sieve},
  booktitle = {The Development of the Number Field Sieve},
  publisher = {Springer},
  series    = {Lecture Notes in Mathematics},
  volume    = {1554},
  year      = {1993},
  doi       = {10.1007/BFb0091539}
}

@inproceedings{impagliazzo2001,
  author    = {Russell Impagliazzo and Ramamohan Paturi and Francis Zane},
  title     = {Which Problems Have Strongly Exponential Complexity?},
  booktitle = {Journal of Computer and System Sciences},
  volume    = {63},
  number    = {4},
  pages     = {512--530},
  year      = {2001},
  doi       = {10.1006/jcss.2001.1774}
}

@article{pan2025,
  author  = {Xi-Wei Pan and Huan-Hai Zhou and Yi-Ming Lu and Jin-Guo Liu},
  title   = {Encoding computationally hard problems in triangular {R}ydberg atom arrays},
  journal = {arXiv preprint},
  year    = {2025},
  eprint  = {2510.25249},
  archivePrefix = {arXiv}
}

@article{canale2023qubo,
  author  = {Eduardo Canale and Claudio Qureshi and Alfredo Viola},
  title   = {Qubo model for the Closest Vector Problem},
  journal = {arXiv preprint},
  year    = {2023},
  eprint  = {2304.03616},
  archivePrefix = {arXiv}
}

@article{goemans1995,
  author  = {Michel X. Goemans and David P. Williamson},
  title   = {Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming},
  journal = {Journal of the ACM},
  volume  = {42},
  number  = {6},
  pages   = {1115--1145},
  year    = {1995},
  doi     = {10.1145/227683.227684}
}

@inproceedings{shor1994,
  author    = {Peter W. Shor},
  title     = {Algorithms for Quantum Computation: Discrete Logarithms and Factoring},
  booktitle = {Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {124--134},
  year      = {1994},
  doi       = {10.1109/SFCS.1994.365700}
}

@article{moonmoser1965,
  author  = {J. W. Moon and L. Moser},
  title   = {On cliques in graphs},
  journal = {Israel Journal of Mathematics},
  volume  = {3},
  number  = {1},
  pages   = {23--28},
  year    = {1965},
  doi     = {10.1007/BF02760024}
}

@inproceedings{lenstra1983,
  author    = {Hendrik W. Lenstra},
  title     = {Integer Programming with a Fixed Number of Variables},
  booktitle = {Mathematics of Operations Research},
  volume    = {8},
  number    = {4},
  pages     = {538--548},
  year      = {1983},
  doi       = {10.1287/moor.8.4.538}
}

@article{epping2004,
  author  = {Thomas Epping and Winfried Hochst\"{a}ttler and Peter Oertel},
  title   = {Complexity results on a paint shop problem},
  journal = {Discrete Applied Mathematics},
  volume  = {136},
  number  = {2--3},
  pages   = {217--226},
  year    = {2004},
  doi     = {10.1016/S0166-218X(03)00442-6}
}

@techreport{vanemde1981,
  author      = {Peter van Emde Boas},
  title       = {Another NP-complete Problem and the Complexity of Computing Short Vectors in a Lattice},
  institution = {Mathematisch Instituut, Universiteit van Amsterdam},
  number      = {81-04},
  year        = {1981}
}

@article{kannan1987,
  author  = {Ravi Kannan},
  title   = {Minkowski's Convex Body Theorem and Integer Programming},
  journal = {Mathematics of Operations Research},
  volume  = {12},
  number  = {3},
  pages   = {415--440},
  year    = {1987},
  doi     = {10.1287/moor.12.3.415}
}

@inproceedings{micciancio2010,
  author    = {Daniele Micciancio and Panagiotis Voulgaris},
  title     = {A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on {V}oronoi Cell Computations},
  booktitle = {Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC)},
  pages     = {351--358},
  year      = {2010},
  doi       = {10.1145/1806689.1806739}
}

@inproceedings{aggarwal2015,
  author    = {Divesh Aggarwal and Daniel Dadush and Noah Stephens-Davidowitz},
  title     = {Solving the Closest Vector Problem in $2^n$ Time -- The Discrete {G}aussian Strikes Again!},
  booktitle = {Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS)},
  pages     = {563--580},
  year      = {2015},
  doi       = {10.1109/FOCS.2015.41}
}

@inproceedings{razgon2007,
  author    = {Igor Razgon},
  title     = {Computing Minimum Directed Feedback Vertex Set in {$O^*(1.9977^n)$}},
  booktitle = {Proceedings of the 10th Italian Conference on Theoretical Computer Science (ICTCS)},
  pages     = {70--81},
  year      = {2007}
}

@article{even1998,
  author  = {Guy Even and Joseph Naor and Baruch Schieber and Madhu Sudan},
  title   = {Approximating Minimum Feedback Sets and Multicuts in Directed Graphs},
  journal = {Algorithmica},
  volume  = {20},
  number  = {2},
  pages   = {151--174},
  year    = {1998},
  doi     = {10.1007/PL00009191}
}

@article{shannon1956,
  author  = {Claude E. Shannon},
  title   = {The zero error capacity of a noisy channel},
  journal = {IRE Transactions on Information Theory},
  volume  = {2},
  number  = {3},
  pages   = {8--19},
  year    = {1956},
  doi     = {10.1109/TIT.1956.1056798}
}

@article{alber2004,
  author  = {Jochen Alber and Jiří Fiala},
  title   = {Geometric separation and exact solutions for the parameterized independent set problem on disk graphs},
  journal = {Journal of Algorithms},
  volume  = {52},
  number  = {2},
  pages   = {134--151},
  year    = {2004},
  doi     = {10.1016/j.jalgor.2003.10.001}
}

@article{dreyfuswagner1971,
  author  = {S. E. Dreyfus and R. A. Wagner},
  title   = {The Steiner Problem in Graphs},
  journal = {Networks},
  volume  = {1},
  number  = {3},
  pages   = {195--207},
  year    = {1971},
  doi     = {10.1002/net.3230010302}
}

@article{byrka2013,
  author  = {Jarosław Byrka and Fabrizio Grandoni and Thomas Rothvoß and Laura Sanità},
  title   = {Steiner Tree Approximation via Iterative Randomized Rounding},
  journal = {Journal of the ACM},
  volume  = {60},
  number  = {1},
  pages   = {1--33},
  year    = {2013},
  doi     = {10.1145/2432622.2432628}
}

@article{horowitz1974,
  author  = {Ellis Horowitz and Sartaj Sahni},
  title   = {Computing Partitions with Applications to the Knapsack Problem},
  journal = {Journal of the ACM},
  volume  = {21},
  number  = {2},
  pages   = {277--292},
  year    = {1974},
  doi     = {10.1145/321812.321823}
}

@article{ibarra1975,
  author  = {Oscar H. Ibarra and Chul E. Kim},
  title   = {Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems},
  journal = {Journal of the ACM},
  volume  = {22},
  number  = {4},
  pages   = {463--468},
  year    = {1975},
  doi     = {10.1145/321906.321909}
}

@article{dahlhaus1994,
  author  = {Elias Dahlhaus and David S. Johnson and Christos H. Papadimitriou and Paul D. Seymour and Mihalis Yannakakis},
  title   = {The Complexity of Multiterminal Cuts},
  journal = {SIAM Journal on Computing},
  volume  = {23},
  number  = {4},
  pages   = {864--894},
  year    = {1994},
  doi     = {10.1137/S0097539292225297}
}

@inproceedings{cao2013,
  author    = {Yixin Cao and Jianer Chen and Jianxin Wang},
  title     = {An Improved Fixed-Parameter Algorithm for the Minimum Weight Multiway Cut Problem},
  booktitle = {Fundamentals of Computation Theory (FCT 2013)},
  pages     = {96--107},
  year      = {2013},
  doi       = {10.1007/978-3-642-40164-0_11}
}

@article{maier1978,
  author  = {David Maier},
  title   = {The Complexity of Some Problems on Subsequences and Supersequences},
  journal = {Journal of the ACM},
  volume  = {25},
  number  = {2},
  pages   = {322--336},
  year    = {1978},
  doi     = {10.1145/322063.322075}
}

@article{wagnerfischer1974,
  author  = {Robert A. Wagner and Michael J. Fischer},
  title   = {The String-to-String Correction Problem},
  journal = {Journal of the ACM},
  volume  = {21},
  number  = {1},
  pages   = {168--173},
  year    = {1974},
  doi     = {10.1145/321796.321811}
}

@article{blum2021,
  author  = {Christian Blum and Maria J. Blesa and Borja Calvo},
  title   = {{ILP}-based reduced variable neighborhood search for the longest common subsequence problem},
  journal = {Computers \& Operations Research},
  volume  = {125},
  pages   = {105089},
  year    = {2021},
  doi     = {10.1016/j.cor.2020.105089}
}

@book{sipser2012,
  author    = {Michael Sipser},
  title     = {Introduction to the Theory of Computation},
  edition   = {3rd},
  publisher = {Cengage Learning},
  year      = {2012}
}

@book{cormen2022,
  author    = {Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022}
}

@article{garey1976,
  author  = {Michael R. Garey and David S. Johnson and Larry Stockmeyer},
  title   = {Some Simplified NP-Complete Graph Problems},
  journal = {Theoretical Computer Science},
  volume  = {1},
  number  = {3},
  pages   = {237--267},
  year    = {1976},
  doi     = {10.1016/0304-3975(76)90059-1}
}

@article{arora2009,
  author  = {Sanjeev Arora and Satish Rao and Umesh Vazirani},
  title   = {Expander Flows, Geometric Embeddings and Graph Partitioning},
  journal = {Journal of the ACM},
  volume  = {56},
  number  = {2},
  pages   = {1--37},
  year    = {2009},
  doi     = {10.1145/1502793.1502794}
}

@techreport{stockmeyer1975setbasis,
  author      = {Larry J. Stockmeyer},
  title       = {The Set Basis Problem Is NP-Complete},
  institution = {IBM Thomas J. Watson Research Center},
  number      = {RC 5431},
  address     = {Yorktown Heights, New York},
  year        = {1975}
}

@article{cygan2014,
  author  = {Marek Cygan and Daniel Lokshtanov and Marcin Pilipczuk and Micha{\l} Pilipczuk and Saket Saurabh},
  title   = {Minimum Bisection Is Fixed Parameter Tractable},
  journal = {SIAM Journal on Computing},
  volume  = {48},
  number  = {2},
  pages   = {417--450},
  year    = {2019},
  note    = {Conference version: STOC 2014},
  doi     = {10.1137/140990255}
}

@article{alon1995,
  author  = {Noga Alon and Raphael Yuster and Uri Zwick},
  title   = {Color-coding},
  journal = {Journal of the ACM},
  volume  = {42},
  number  = {4},
  pages   = {844--856},
  year    = {1995},
  doi     = {10.1145/210332.210337}
}

@inproceedings{bjorklund2007,
  author    = {Andreas Bj\"{o}rklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto},
  title     = {Fourier Meets M\"{o}bius: Fast Subset Convolution},
  booktitle = {Proceedings of the 39th ACM Symposium on Theory of Computing (STOC)},
  pages     = {67--74},
  year      = {2007},
  doi       = {10.1145/1250790.1250801}
}

@article{johnson1983,
  author  = {David S. Johnson and Kenneth A. Niemi},
  title   = {On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees},
  journal = {Mathematics of Operations Research},
  volume  = {8},
  number  = {1},
  pages   = {1--14},
  year    = {1983},
  doi     = {10.1287/moor.8.1.1}
}

@article{kolliopoulos2007,
  author  = {Stavros G. Kolliopoulos and George Steiner},
  title   = {Partially Ordered Knapsack and Applications to Scheduling},
  journal = {Discrete Applied Mathematics},
  volume  = {155},
  number  = {8},
  pages   = {889--897},
  year    = {2007},
  doi     = {10.1016/j.dam.2006.09.003}
}

@inproceedings{nederlof2009,
  author    = {Jesper Nederlof},
  title     = {Fast Polynomial-Space Algorithms Using {M\"{o}bius} Inversion: Improving on {Steiner} Tree and Related Problems},
  booktitle = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP)},
  series    = {LNCS},
  volume    = {5555},
  pages     = {713--725},
  year      = {2009},
  doi       = {10.1007/978-3-642-02927-1_59}
}

@article{raiha1981,
  author  = {Kari-Jouko R{\"a}ih{\"a} and Esko Ukkonen},
  title   = {The Shortest Common Supersequence Problem over Binary Alphabet is {NP}-Complete},
  journal = {Theoretical Computer Science},
  volume  = {16},
  number  = {2},
  pages   = {187--198},
  year    = {1981},
  doi     = {10.1016/0304-3975(81)90075-X}
}

@article{bodlaender2012,
  author  = {Hans L. Bodlaender and Fedor V. Fomin and Arie M. C. A. Koster and Dieter Kratsch and Dimitrios M. Thilikos},
  title   = {A Note on Exact Algorithms for Vertex Ordering Problems on Graphs},
  journal = {Theory of Computing Systems},
  volume  = {50},
  number  = {3},
  pages   = {420--432},
  year    = {2012},
  doi     = {10.1007/s00224-011-9312-0}
}

@article{booth1976,
  author  = {Booth, Kellogg S. and Lueker, George S.},
  title   = {Testing for the consecutive ones property, interval graphs, and graph planarity using {PQ}-tree algorithms},
  journal = {Journal of Computer and System Sciences},
  volume  = {13},
  number  = {3},
  pages   = {335--379},
  year    = {1976}
}

@phdthesis{booth1975,
  author  = {Booth, Kellogg S.},
  title   = {{PQ}-Tree Algorithms},
  school  = {University of California, Berkeley},
  year    = {1975}
}

@article{chopra1993,
  author  = {Sunil Chopra and M. R. Rao},
  title   = {The partition problem},
  journal = {Mathematical Programming},
  volume  = {59},
  number  = {1--3},
  pages   = {87--115},
  year    = {1993},
  doi     = {10.1007/BF01581239}
}

@article{chopra1996,
  author  = {Sunil Chopra and Jonathan H. Owen},
  title   = {Extended formulations for the A-cut problem},
  journal = {Mathematical Programming},
  volume  = {73},
  pages   = {7--30},
  year    = {1996},
  doi     = {10.1007/BF02592096}
}

@article{boothlueker1976,
  author  = {Kellogg S. Booth and George S. Lueker},
  title   = {Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using {PQ}-Tree Algorithms},
  journal = {Journal of Computer and System Sciences},
  volume  = {13},
  number  = {3},
  pages   = {335--379},
  year    = {1976},
  doi     = {10.1016/S0022-0000(76)80045-1}
}

@inproceedings{chandra1977,
  author    = {Ashok K. Chandra and Philip M. Merlin},
  title     = {Optimal Implementation of Conjunctive Queries in Relational Data Bases},
  booktitle = {Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC)},
  pages     = {77--90},
  year      = {1977},
  doi       = {10.1145/800105.803397}
}

@article{chen2008,
  author  = {Jianer Chen and Yang Liu and Songjian Lu and Barry O'Sullivan and Igor Razgon},
  title   = {A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem},
  journal = {Journal of the ACM},
  volume  = {55},
  number  = {5},
  pages   = {1--19},
  year    = {2008},
  doi     = {10.1145/1411509.1411511}
}

@article{coffman1972,
  author  = {Edward G. Coffman and Ronald L. Graham},
  title   = {Optimal Scheduling for Two-Processor Systems},
  journal = {Acta Informatica},
  volume  = {1},
  number  = {3},
  pages   = {200--213},
  year    = {1972},
  doi     = {10.1007/BF00288685}
}

@article{codycoffman1976,
  author  = {R. A. Cody and E. G. Coffman, Jr.},
  title   = {Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices},
  journal = {Journal of the ACM},
  volume  = {23},
  number  = {1},
  pages   = {103--115},
  year    = {1976},
  doi     = {10.1145/321921.321933}
}

@inproceedings{cordella2004,
  author    = {Luigi P. Cordella and Pasquale Foggia and Carlo Sansone and Mario Vento},
  title     = {A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs},
  booktitle = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  volume    = {26},
  number    = {10},
  pages     = {1367--1372},
  year      = {2004},
  doi       = {10.1109/TPAMI.2004.75}
}

@article{eppstein1992,
  author  = {David Eppstein},
  title   = {Finding the $k$ Smallest Spanning Trees},
  journal = {BIT},
  volume  = {32},
  number  = {2},
  pages   = {237--248},
  year    = {1992},
  doi     = {10.1007/BF01994880}
}

@article{even1976,
  author  = {Shimon Even and Alon Itai and Adi Shamir},
  title   = {On the Complexity of Timetable and Multicommodity Flow Problems},
  journal = {SIAM Journal on Computing},
  volume  = {5},
  number  = {4},
  pages   = {691--703},
  year    = {1976},
  doi     = {10.1137/0205048}
}

@article{frederickson1979,
  author  = {Greg N. Frederickson},
  title   = {Approximation Algorithms for Some Postman Problems},
  journal = {Journal of the ACM},
  volume  = {26},
  number  = {3},
  pages   = {538--554},
  year    = {1979},
  doi     = {10.1145/322139.322150}
}

@article{frederickson1978routing,
  author  = {Greg N. Frederickson and Matthew S. Hecht and Chul E. Kim},
  title   = {Approximation Algorithms for Some Routing Problems},
  journal = {SIAM Journal on Computing},
  volume  = {7},
  number  = {2},
  pages   = {178--193},
  year    = {1978},
  doi     = {10.1137/0207017}
}

@article{fredericksonguan1993,
  author  = {Greg N. Frederickson and Da-Wei Guan},
  title   = {Nonpreemptive Ensemble Motion Planning on a Tree},
  journal = {Journal of Algorithms},
  volume  = {15},
  number  = {1},
  pages   = {29--60},
  year    = {1993}
}

@article{gottlob2002,
  author  = {Georg Gottlob and Nicola Leone and Francesco Scarcello},
  title   = {Hypertree Decompositions and Tractable Queries},
  journal = {Journal of Computer and System Sciences},
  volume  = {64},
  number  = {3},
  pages   = {579--627},
  year    = {2002},
  doi     = {10.1006/jcss.2001.1809}
}

@article{haddadi2008,
  author  = {Salim Haddadi and Zohra Layouni},
  title   = {Consecutive block minimization is 1.5-approximable},
  journal = {Information Processing Letters},
  volume  = {108},
  number  = {3},
  pages   = {161--163},
  year    = {2008},
  doi     = {10.1016/j.ipl.2008.05.003}
}

@techreport{Heidari2022,
  author      = {Heidari, Shahrokh and Dinneen, Michael J. and Delmas, Patrice},
  title       = {An Equivalent {QUBO} Model to the Minimum Multi-Way Cut Problem},
  institution = {Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland},
  year        = {2022},
  number      = {CDMTCS-565}
}

@article{hu1961,
  author  = {Te Chiang Hu},
  title   = {Parallel Sequencing and Assembly Line Problems},
  journal = {Operations Research},
  volume  = {9},
  number  = {6},
  pages   = {841--848},
  year    = {1961},
  doi     = {10.1287/opre.9.6.841}
}

@article{adolphsonHu1973,
  author  = {Donald Adolphson and Te Chiang Hu},
  title   = {Optimal Linear Ordering},
  journal = {SIAM Journal on Applied Mathematics},
  volume  = {25},
  number  = {3},
  pages   = {403--423},
  year    = {1973},
  doi     = {10.1137/0125040}
}

@inproceedings{kolaitis1998,
  author    = {Phokion G. Kolaitis and Moshe Y. Vardi},
  title     = {Conjunctive-Query Containment and Constraint Satisfaction},
  booktitle = {Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS)},
  pages     = {205--213},
  year      = {1998},
  doi       = {10.1145/275487.275511}
}

@article{kou1977,
  author  = {Lawrence T. Kou},
  title   = {Polynomial Complete Consecutive Information Retrieval Problems},
  journal = {SIAM Journal on Computing},
  volume  = {6},
  number  = {1},
  pages   = {67--75},
  year    = {1977},
  doi     = {10.1137/0206005}
}

@article{lawler1972,
  author  = {Eugene L. Lawler},
  title   = {A Procedure for Computing the $K$ Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem},
  journal = {Management Science},
  volume  = {18},
  number  = {7},
  pages   = {401--405},
  year    = {1972},
  doi     = {10.1287/mnsc.18.7.401}
}

@article{lenstra1976,
  author  = {Jan Karel Lenstra and Alexander H. G. Rinnooy Kan},
  title   = {On General Routing Problems},
  journal = {Networks},
  volume  = {6},
  number  = {3},
  pages   = {273--280},
  year    = {1976},
  doi     = {10.1002/net.3230060305}
}

@article{lenstra1978,
  author  = {Jan Karel Lenstra and Alexander H. G. Rinnooy Kan},
  title   = {Complexity of Scheduling under Precedence Constraints},
  journal = {Operations Research},
  volume  = {26},
  number  = {1},
  pages   = {22--35},
  year    = {1978},
  doi     = {10.1287/opre.26.1.22}
}

@inproceedings{lipski1977fct,
  author    = {Witold Lipski Jr.},
  title     = {Two {NP}-Complete Problems Related to Information Retrieval},
  booktitle = {Fundamentals of Computation Theory (FCT 1977)},
  series    = {Lecture Notes in Computer Science},
  volume    = {56},
  pages     = {452--458},
  publisher = {Springer},
  year      = {1977},
  doi       = {10.1007/3-540-08442-8_115}
}

@article{lucchesi1978,
  author  = {Cl\'audio L. Lucchesi and Daniel H. Younger},
  title   = {A Minimax Theorem for Directed Graphs},
  journal = {Journal of the London Mathematical Society},
  volume  = {s2-17},
  number  = {3},
  pages   = {369--374},
  year    = {1978},
  doi     = {10.1112/jlms/s2-17.3.369}
}

@article{lucchesi1978keys,
  author  = {Cl\'audio L. Lucchesi and Sylvia L. Osborn},
  title   = {Candidate Keys for Relations},
  journal = {Journal of Computer and System Sciences},
  volume  = {17},
  number  = {2},
  pages   = {270--279},
  year    = {1978},
  doi     = {10.1016/0022-0000(78)90009-0}
}

@article{papadimitriou1982,
  author  = {Christos H. Papadimitriou and Mihalis Yannakakis},
  title   = {The Complexity of Restricted Spanning Tree Problems},
  journal = {Journal of the ACM},
  volume  = {29},
  number  = {2},
  pages   = {285--309},
  year    = {1982},
  doi     = {10.1145/322307.322309}
}

@inproceedings{papadimitriou1979,
  author    = {Christos H. Papadimitriou and Mihalis Yannakakis},
  title     = {Scheduling Interval-Ordered Tasks},
  booktitle = {Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC)},
  pages     = {1--7},
  year      = {1979},
  doi       = {10.1145/800135.804393}
}

@book{papadimitriou-steiglitz1982,
  author    = {Christos H. Papadimitriou and Kenneth Steiglitz},
  title     = {Combinatorial Optimization: Algorithms and Complexity},
  publisher = {Prentice-Hall},
  address   = {Englewood Cliffs, NJ},
  year      = {1982}
}

@article{schaefer1978,
  author  = {Thomas J. Schaefer},
  title   = {The Complexity of Satisfiability Problems},
  journal = {Conference Record of the 10th Annual ACM Symposium on Theory of Computing (STOC)},
  pages   = {216--226},
  year    = {1978},
  doi     = {10.1145/800133.804350}
}

@article{wong1984steiner,
  author  = {R. T. Wong},
  title   = {A Dual Ascent Approach for Steiner Tree Problems on a Directed Graph},
  journal = {Mathematical Programming},
  volume  = {28},
  number  = {3},
  pages   = {271--287},
  year    = {1984},
  doi     = {10.1007/BF02612335}
}

@article{kochmartin1998steiner,
  author  = {Thorsten Koch and Alexander Martin},
  title   = {Solving Steiner Tree Problems in Graphs to Optimality},
  journal = {Networks},
  volume  = {32},
  number  = {3},
  pages   = {207--232},
  year    = {1998},
  doi     = {10.1002/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O}
}

@inproceedings{stockmeyer1973,
  author    = {Larry J. Stockmeyer and Albert R. Meyer},
  title     = {Word Problems Requiring Exponential Time: Preliminary Report},
  booktitle = {Proceedings of the 5th Annual ACM Symposium on Theory of Computing (STOC)},
  pages     = {1--9},
  year      = {1973},
  doi       = {10.1145/800125.804029}
}

@article{ullman1975,
  author  = {Jeffrey D. Ullman},
  title   = {NP-Complete Scheduling Problems},
  journal = {Journal of Computer and System Sciences},
  volume  = {10},
  number  = {3},
  pages   = {384--393},
  year    = {1975},
  doi     = {10.1016/S0022-0000(75)80008-0}
}

@inproceedings{williams2002,
  author    = {Ryan Williams},
  title     = {Algorithms for Quantified Boolean Formulas},
  booktitle = {Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  pages     = {299--307},
  year      = {2002}
}

@article{papadimitriou1976edge,
  author  = {Christos H. Papadimitriou},
  title   = {On the Complexity of Edge Traversing},
  journal = {Journal of the ACM},
  volume  = {23},
  number  = {3},
  pages   = {544--554},
  year    = {1976}
}

@article{edmondsjohnson1973,
  author  = {Jack Edmonds and Ellis L. Johnson},
  title   = {Matching, Euler Tours and the Chinese Postman},
  journal = {Mathematical Programming},
  volume  = {5},
  pages   = {88--124},
  year    = {1973}
}

@inproceedings{charikar2005,
  author    = {Moses Charikar and Eric Lehman and Ding Liu and Rina Panigrahy and Manoj Prabhakaran and Amit Sahai and Abhi Shelat},
  title     = {The Smallest Grammar Problem},
  booktitle = {IEEE Transactions on Information Theory},
  volume    = {51},
  number    = {7},
  pages     = {2554--2576},
  year      = {2005}
}

@article{lenstra1977,
  author  = {J. K. Lenstra and A. H. G. Rinnooy Kan and P. Brucker},
  title   = {Complexity of Machine Scheduling Problems},
  journal = {Annals of Discrete Mathematics},
  volume  = {1},
  pages   = {343--362},
  year    = {1977},
  doi     = {10.1016/S0167-5060(08)70743-X}
}

@book{conway1967,
  author    = {Richard W. Conway and William L. Maxwell and Louis W. Miller},
  title     = {Theory of Scheduling},
  publisher = {Addison-Wesley},
  year      = {1967}
}

@article{horn1973,
  author  = {W. A. Horn},
  title   = {Minimizing Average Flow Time with Parallel Machines},
  journal = {Operations Research},
  volume  = {21},
  number  = {3},
  pages   = {846--847},
  year    = {1973}
}

@techreport{plaisted1976,
  author      = {David A. Plaisted},
  title       = {Some Polynomial and Integer Divisibility Problems Are {NP}-Hard},
  institution = {Stanford University, Department of Computer Science},
  number      = {STAN-CS-76-583},
  year        = {1976}
}

@article{Streif2021,
  title   = {Beating classical heuristics for the binary paint shop problem
             with the quantum approximate optimization algorithm},
  author  = {Streif, Michael and Yarkoni, Sheir and Skolik, Andrea
             and Neukart, Florian and Leib, Martin},
  journal = {Physical Review A},
  volume  = {104},
  pages   = {012403},
  year    = {2021},
  doi     = {10.1103/PhysRevA.104.012403}
}

@techreport{storer1977,
  author      = {James A. Storer},
  title       = {NP-Completeness Results Concerning Data Compression},
  institution = {Princeton University, Department of Electrical Engineering and Computer Science},
  number      = {234},
  year        = {1977}
}

@article{storer1982,
  author  = {James A. Storer and Thomas G. Szymanski},
  title   = {Data Compression via Textual Substitution},
  journal = {Journal of the ACM},
  volume  = {29},
  number  = {4},
  pages   = {928--951},
  year    = {1982}
}

@article{haase2016,
  author  = {Haase, Christoph and Kiefer, Stefan},
  title   = {The Complexity of the {K}th Largest Subset Problem and Related Problems},
  journal = {Information Processing Letters},
  volume  = {116},
  number  = {2},
  pages   = {111--115},
  year    = {2016}
}

@article{Murty1972,
  author  = {Murty, Katta G.},
  title   = {A fundamental problem in linear inequalities with applications to the travelling salesman problem},
  journal = {Mathematical Programming},
  year    = {1972},
  volume  = {3},
  pages   = {326--370},
  doi     = {10.1007/BF01584550}
}

@article{gonzalez1976,
  author  = {Teofilo Gonzalez and Sartaj Sahni},
  title   = {Open Shop Scheduling to Minimize Finish Time},
  journal = {Journal of the ACM},
  volume  = {23},
  number  = {4},
  pages   = {665--679},
  year    = {1976},
  doi     = {10.1145/321978.321985}
}

@article{yannakakis1980,
  author  = {Mihalis Yannakakis and Fanica Gavril},
  title   = {Edge Dominating Sets in Graphs},
  journal = {SIAM Journal on Applied Mathematics},
  volume  = {38},
  number  = {3},
  pages   = {364--372},
  year    = {1980},
  doi     = {10.1137/0138030}
}

@inproceedings{edmonds1970,
  author    = {Jack Edmonds},
  title     = {Submodular functions, matroids, and certain polyhedra},
  booktitle = {Combinatorial Structures and Their Applications},
  pages     = {69--87},
  year      = {1970},
  publisher = {Gordon and Breach}
}

@article{doron2024,
  author  = {Ilan Doron-Arad and Ariel Kulik and Hadas Shachnai},
  title   = {You (Almost) Can't Beat Brute Force for 3-Matroid Intersection},
  journal = {arXiv preprint arXiv:2412.02217},
  year    = {2024}
}

@article{fomin2019,
  author  = {Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh},
  title   = {Exact Algorithms via Monotone Local Search},
  journal = {Journal of the ACM},
  volume  = {66},
  number  = {2},
  pages   = {1--23},
  year    = {2019},
  doi     = {10.1145/3277568}
}