Summary
Complete catalog of 204 problem models and 149 reduction rules extracted from Garey & Johnson's Computers and Intractability: A Guide to the Theory of NP-Completeness (1979). All definitions are stored as structured issue templates in references/Garey&Johnson/issues/.
This serves as the master reference for the G&J extraction effort. Each file can be submitted as a GitHub issue to drive implementation via the issue-to-pr skill.
Problem Models (204)
Chapter 3 — Core NP-Complete Problems (P02–P24)
| ID |
Name |
G&J Ref |
| P02 |
ThreeDimensionalMatching |
§3.1.2 |
| P06 |
HamiltonianCircuit |
§3.1.4 |
| P07 |
Partition |
§3.2.1 |
| P08 |
ExactCoverBy3Sets |
§3.1.2 |
| P09 |
HamiltonianPath |
§3.2.1 |
| P10 |
HamiltonianPathBetweenTwoPoints |
§3.2.1 |
| P11 |
DirectedHamiltonianCircuit |
§3.2.1 |
| P12 |
DirectedHamiltonianPath |
§3.2.1 |
| P13 |
MinimumCover |
§3.2.1 |
| P14 |
HittingSet |
§3.2.1 |
| P15 |
SubgraphIsomorphism |
§3.2.1 |
| P16 |
BoundedDegreeSpanningTree |
§3.2.1 |
| P17 |
MinimumEquivalentDigraph |
§3.2.1 |
| P18 |
Knapsack |
§3.2.1 |
| P19 |
MultiprocessorScheduling |
§3.2.1 |
| P20 |
EnsembleComputation |
§3.2.2 |
| P21 |
PartitionIntoTriangles |
§3.2.2 |
| P22 |
SequencingWithinIntervals |
§3.2.2 |
| P23 |
MinimumTestCollection |
§3.2.2 |
| P24 |
MinimumTardinessSequencing |
§3.2.2 |
Chapter 3 — Exercises (P25–P34)
| ID |
Name |
G&J Ref |
| P25 |
LongestPath |
GT23 |
| P26 |
PartitionIntoHamiltonianSubgraphs |
GT13 |
| P27 |
LargestCommonSubgraph |
GT49 |
| P28 |
MinimumSumOfSquares |
SP12 |
| P29 |
FeedbackVertexSet |
GT7 |
| P30 |
ExactCoverBy4Sets |
SP3 |
| P31 |
SteinerTree |
ND12 |
| P32 |
StarFreeRegexInequivalence |
AL4 |
| P33 |
SetSplitting |
SP4 |
| P34 |
PartitionIntoPathsOfLength2 |
GT11 |
Appendix A1 — Graph Theory (P35–P85)
| ID |
Name |
G&J Ref |
| P35 |
GraphGrundyNumbering |
GT56 |
| P36 |
DomaticNumber |
GT3 |
| P37 |
AchromaticNumber |
GT5 |
| P38 |
MonochromaticTriangle |
GT6 |
| P39 |
FeedbackArcSet |
GT8 |
| P40 |
PartialFeedbackEdgeSet |
GT9 |
| P41 |
MinimumMaximalMatching |
GT10 |
| P42 |
PartitionIntoIsomorphicSubgraphs |
GT12 |
| P43 |
PartitionIntoForests |
GT14 |
| P44 |
PartitionIntoCliques |
GT15 |
| P45 |
PartitionIntoPerfectMatchings |
GT16 |
| P46 |
CoveringByCliques |
GT17 |
| P47 |
CoveringByCompleteBipartiteSubgraphs |
GT18 |
| P48 |
InducedSubgraphWithProperty |
GT21 |
| P49 |
InducedConnectedSubgraphWithProperty |
GT22 |
| P50 |
InducedPath |
GT23 |
| P51 |
BalancedCompleteBipartiteSubgraph |
GT24 |
| P52 |
BipartiteSubgraph |
GT25 |
| P53 |
DegreeBoundedConnectedSubgraph |
GT26 |
| P54 |
PlanarSubgraph |
GT27 |
| P55 |
EdgeSubgraph |
GT28 |
| P56 |
TransitiveSubgraph |
GT29 |
| P57 |
UniconnectedSubgraph |
GT30 |
| P58 |
MinimumKConnectedSubgraph |
GT31 |
| P59 |
CubicSubgraph |
GT32 |
| P60 |
HamiltonianCompletion |
GT34 |
| P61 |
IntervalGraphCompletion |
GT35 |
| P62 |
PathGraphCompletion |
GT36 |
| P63 |
Bandwidth |
GT40 |
| P64 |
DirectedBandwidth |
GT41 |
| P65 |
OptimalLinearArrangement |
GT42 |
| P66 |
DirectedOptimalLinearArrangement |
GT43 |
| P67 |
MinimumCutLinearArrangement |
GT44 |
| P68 |
RootedTreeArrangement |
GT45 |
| P69 |
DirectedEliminationOrdering |
GT46 |
| P70 |
EliminationDegreeSequence |
GT47 |
| P71 |
MaximumSubgraphMatching |
GT50 |
| P72 |
GraphContractability |
GT51 |
| P73 |
GraphHomomorphism |
GT52 |
| P74 |
DigraphDMorphism |
GT53 |
| P75 |
PathWithForbiddenPairs |
GT54 |
| P76 |
MultipleChoiceMatching |
GT55 |
| P77 |
Kernel |
GT57 |
| P78 |
KClosure |
GT58 |
| P79 |
IntersectionGraphBasis |
GT59 |
| P80 |
PathDistinguishers |
GT60 |
| P81 |
MetricDimension |
GT61 |
| P82 |
NesetrilRodlDimension |
GT62 |
| P83 |
ThresholdNumber |
GT63 |
| P84 |
OrientedDiameter |
GT64 |
| P85 |
WeightedDiameter |
GT65 |
Appendix A2 — Network Design (P86–P132)
| ID |
Name |
G&J Ref |
| P86 |
DegreeConstrainedSpanningTree |
ND1 |
| P87 |
MaximumLeafSpanningTree |
ND2 |
| P88 |
ShortestTotalPathLengthSpanningTree |
ND3 |
| P89 |
BoundedDiameterSpanningTree |
ND4 |
| P90 |
CapacitatedSpanningTree |
ND5 |
| P91 |
GeometricCapacitatedSpanningTree |
ND6 |
| P92 |
OptimumCommunicationSpanningTree |
ND7 |
| P93 |
IsomorphicSpanningTree |
ND8 |
| P94 |
KthBestSpanningTree |
ND9 |
| P95 |
BoundedComponentSpanningForest |
ND10 |
| P96 |
MultipleChoiceBranching |
ND11 |
| P97 |
GeometricSteinerTree |
ND13 |
| P98 |
GraphPartitioning |
ND14 |
| P99 |
AcyclicPartition |
ND15 |
| P100 |
MinimumCutIntoBoundedSets |
ND17 |
| P101 |
BiconnectivityAugmentation |
ND18 |
| P102 |
StrongConnectivityAugmentation |
ND19 |
| P103 |
NetworkReliability |
ND20 |
| P104 |
NetworkSurvivability |
ND21 |
| P105 |
GeometricTravelingSalesman |
ND23 |
| P106 |
BottleneckTravelingSalesman |
ND24 |
| P107 |
ChinesePostmanMixedGraphs |
ND25 |
| P108 |
StackerCrane |
ND26 |
| P109 |
RuralPostman |
ND27 |
| P110 |
LongestCircuit |
ND28 |
| P111 |
ShortestWeightConstrainedPath |
ND30 |
| P112 |
KthShortestPath |
ND31 |
| P113 |
MinimumEdgeCostFlow |
ND32 |
| P114 |
IntegralFlowWithMultipliers |
ND33 |
| P115 |
PathConstrainedNetworkFlow |
ND34 |
| P116 |
IntegralFlowWithHomologousArcs |
ND35 |
| P117 |
IntegralFlowWithBundles |
ND36 |
| P118 |
UndirectedFlowWithLowerBounds |
ND37 |
| P119 |
DirectedTwoCommodityIntegralFlow |
ND38 |
| P120 |
UndirectedTwoCommodityIntegralFlow |
ND39 |
| P121 |
DisjointConnectingPaths |
ND40 |
| P122 |
MaximumLengthBoundedDisjointPaths |
ND41 |
| P123 |
MaximumFixedLengthDisjointPaths |
ND42 |
| P124 |
QuadraticAssignment |
ND43 |
| P125 |
MinimizingDummyActivitiesPERT |
ND44 |
| P126 |
ConstrainedTriangulation |
ND45 |
| P127 |
IntersectionGraphSegmentsGrid |
ND46 |
| P128 |
EdgeEmbeddingOnGrid |
ND47 |
| P129 |
GeometricConnectedDominatingSet |
ND48 |
| P130 |
MinimumBroadcastTime |
ND49 |
| P131 |
MinMaxMulticenter |
ND50 |
| P132 |
MinSumMulticenter |
ND51 |
Appendix A3 — Sets and Partitions (P133–P144)
| ID |
Name |
G&J Ref |
| P133 |
SetBasis |
SP7 |
| P134 |
IntersectionPattern |
SP9 |
| P135 |
ComparativeContainment |
SP10 |
| P136 |
ThreeMatroidIntersection |
SP11 |
| P137 |
SubsetSum |
SP13 |
| P138 |
SubsetProduct |
SP14 |
| P139 |
ThreePartition |
SP15 |
| P140 |
Numerical3DimensionalMatching |
SP16 |
| P141 |
NumericalMatchingTargetSums |
SP17 |
| P142 |
ExpectedComponentSum |
SP18 |
| P143 |
KthLargestSubset |
SP20 |
| P144 |
KthLargestMTuple |
SP21 |
Appendix A4 — Storage and Retrieval (P145–P187)
| ID |
Name |
G&J Ref |
| P145 |
DynamicStorageAllocation |
SR2 |
| P146 |
PrunedTrieSpaceMinimization |
SR3 |
| P155 |
ExpectedRetrievalCost |
SR4 |
| P156 |
RootedTreeStorageAssignment |
SR5 |
| P157 |
MultipleCopyFileAllocation |
SR6 |
| P158 |
CapacityAssignment |
SR7 |
| P159 |
ShortestCommonSupersequence |
SR8 |
| P160 |
ShortestCommonSuperstring |
SR9 |
| P161 |
LongestCommonSubsequence |
SR10 |
| P162 |
BoundedPostCorrespondenceProblem |
SR11 |
| P163 |
HittingString |
SR12 |
| P164 |
SparseMatrixCompression |
SR13 |
| P165 |
ConsecutiveOnesSubmatrix |
SR14 |
| P166 |
ConsecutiveOnesMatrixPartition |
SR15 |
| P167 |
ConsecutiveOnesMatrixAugmentation |
SR16 |
| P168 |
ConsecutiveBlockMinimization |
SR17 |
| P169 |
ConsecutiveSets |
SR18 |
| P170 |
TwoDimensionalConsecutiveSets |
SR19 |
| P171 |
StringToStringCorrection |
SR20 |
| P172 |
GroupingBySwapping |
SR21 |
| P173 |
ExternalMacroDataCompression |
SR22 |
| P174 |
InternalMacroDataCompression |
SR23 |
| P175 |
RegularExpressionSubstitution |
SR24 |
| P176 |
RectilinearPictureCompression |
SR25 |
| P177 |
MinimumCardinalityKey |
SR26 |
| P178 |
AdditionalKey |
SR27 |
| P179 |
PrimeAttributeName |
SR28 |
| P180 |
BoyceCoddNormalFormViolation |
SR29 |
| P181 |
ConjunctiveQueryFoldability |
SR30 |
| P182 |
ConjunctiveBooleanQuery |
SR31 |
| P183 |
TableauEquivalence |
SR32 |
| P184 |
SerializabilityOfDatabaseHistories |
SR33 |
| P185 |
SafetyOfDatabaseTransactionSystems |
SR34 |
| P186 |
ConsistencyOfDatabaseFrequencyTables |
SR35 |
| P187 |
SafetyOfFileProtectionSystems |
SR36 |
Appendix A5 — Sequencing and Scheduling (P188–P208)
| ID |
Name |
G&J Ref |
| P188 |
SequencingWithReleaseTimesAndDeadlines |
SS1 |
| P189 |
SequencingToMinimizeTardyTasks |
SS2 |
| P190 |
SequencingToMinimizeTardyTaskWeight |
SS3 |
| P191 |
SequencingToMinimizeWeightedCompletionTime |
SS4 |
| P192 |
SequencingToMinimizeWeightedTardiness |
SS5 |
| P193 |
SequencingWithDeadlinesAndSetupTimes |
SS6 |
| P194 |
SequencingToMinimizeMaximumCumulativeCost |
SS7 |
| P195 |
PrecedenceConstrainedScheduling |
SS9 |
| P196 |
ResourceConstrainedScheduling |
SS10 |
| P197 |
SchedulingWithIndividualDeadlines |
SS11 |
| P198 |
PreemptiveScheduling |
SS12 |
| P199 |
SchedulingToMinimizeWeightedCompletionTime |
SS13 |
| P200 |
OpenShopScheduling |
SS14 |
| P201 |
FlowShopScheduling |
SS15 |
| P202 |
NoWaitFlowShopScheduling |
SS16 |
| P203 |
TwoProcessorFlowShopWithBoundedBuffer |
SS17 |
| P204 |
JobShopScheduling |
SS18 |
| P205 |
TimetableDesign |
SS19 |
| P206 |
StaffScheduling |
SS20 |
| P207 |
ProductionPlanning |
SS21 |
| P208 |
DeadlockAvoidance |
SS22 |
Appendix A6 — Mathematical Programming (P209–P216)
| ID |
Name |
G&J Ref |
| P209 |
IntegerProgramming |
MP1 |
| P210 |
QuadraticProgramming |
MP2 |
| P211 |
CostParametricLinearProgramming |
MP3 |
| P212 |
FeasibleBasisExtension |
MP4 |
| P213 |
MinimumWeightSolutionLinearEquations |
MP5 |
| P214 |
OpenHemisphere |
MP6 |
| P215 |
KRelevancy |
MP7 |
| P216 |
TravelingSalesmanPolytopeNonAdjacency |
MP8 |
Reduction Rules (149)
Core Reductions — Chapter 3 (R02–R24)
| ID |
Source |
Target |
| R02 |
KSatisfiability |
ThreeDimensionalMatching |
| R03 |
ThreeDimensionalMatching |
ExactCoverBy3Sets |
| R05 |
MinimumVertexCover |
MaximumClique |
| R06 |
KSatisfiability |
MinimumVertexCover |
| R07 |
MinimumVertexCover |
HamiltonianCircuit |
| R08 |
HamiltonianCircuit |
HamiltonianPath |
| R09 |
HamiltonianCircuit |
DirectedHamiltonianCircuit |
| R10 |
ThreeDimensionalMatching |
Partition |
| R11 |
ExactCoverBy3Sets |
MinimumCover |
| R12 |
MinimumVertexCover |
HittingSet |
| R13 |
MaximumClique |
SubgraphIsomorphism |
| R14 |
HamiltonianPath |
BoundedDegreeSpanningTree |
| R15 |
DirectedHamiltonianCircuit |
MinimumEquivalentDigraph |
| R16 |
Partition |
Knapsack |
| R17 |
Partition |
MultiprocessorScheduling |
| R18 |
MinimumVertexCover |
EnsembleComputation |
| R19 |
ExactCoverBy3Sets |
PartitionIntoTriangles |
| R20 |
Partition |
SequencingWithinIntervals |
| R21 |
ThreeDimensionalMatching |
MinimumTestCollection |
| R22 |
MaximumClique |
MinimumTardinessSequencing |
| R23 |
MinimumVertexCover |
FeedbackVertexSet |
| R24 |
MinimumVertexCover |
FeedbackArcSet |
Graph Theory Reductions (R25–R71)
| ID |
Source |
Target |
| R25 |
KSatisfiability |
MaximumClique |
| R26 |
MaximumClique |
BalancedCompleteBipartiteSubgraph |
| R27 |
ExactCoverBy3Sets |
GeometricCapacitatedSpanningTree |
| R28 |
ExactCoverBy3Sets |
OptimumCommunicationSpanningTree |
| R29 |
HamiltonianPath |
IsomorphicSpanningTree |
| R30 |
HamiltonianPath |
KthBestSpanningTree |
| R31 |
PartitionIntoPathsOfLength2 |
BoundedComponentSpanningForest |
| R32 |
KSatisfiability |
MultipleChoiceBranching |
| R33 |
ExactCoverBy3Sets |
SteinerTree |
| R34 |
ExactCoverBy3Sets |
GeometricSteinerTree |
| R35 |
PartitionIntoTriangles |
GraphPartitioning |
| R36 |
ExactCoverBy3Sets |
AcyclicPartition |
| R37 |
Maximum2Satisfiability |
MaxCut |
| R38 |
SimpleMaxCut |
MinimumCutIntoBoundedSets |
| R39 |
HamiltonianCircuit |
BiconnectivityAugmentation |
| R40 |
HamiltonianCircuit |
StrongConnectivityAugmentation |
| R41 |
SteinerTree |
NetworkReliability |
| R42 |
MinimumVertexCover |
NetworkSurvivability |
| R43 |
HamiltonianCircuit |
TravelingSalesman |
| R44 |
ExactCoverBy3Sets |
GeometricTravelingSalesman |
| R45 |
HamiltonianCircuit |
BottleneckTravelingSalesman |
| R46 |
KSatisfiability |
ChinesePostmanMixedGraphs |
| R47 |
HamiltonianCircuit |
StackerCrane |
| R48 |
HamiltonianCircuit |
RuralPostman |
| R49 |
HamiltonianCircuit |
LongestCircuit |
| R50 |
HamiltonianPathBetweenTwoPoints |
LongestPath |
| R51 |
Partition |
ShortestWeightConstrainedPath |
| R52 |
HamiltonianPath |
KthShortestPath |
| R53 |
ExactCoverBy3Sets |
MinimumEdgeCostFlow |
| R54 |
Partition |
IntegralFlowWithMultipliers |
| R55 |
KSatisfiability |
PathConstrainedNetworkFlow |
| R56 |
KSatisfiability |
IntegralFlowWithHomologousArcs |
| R57 |
MaximumIndependentSet |
IntegralFlowWithBundles |
| R58 |
Satisfiability |
UndirectedFlowWithLowerBounds |
| R59 |
KSatisfiability |
DirectedTwoCommodityIntegralFlow |
| R60 |
DirectedTwoCommodityIntegralFlow |
UndirectedTwoCommodityIntegralFlow |
| R61 |
KSatisfiability |
DisjointConnectingPaths |
| R62 |
KSatisfiability |
MaximumLengthBoundedDisjointPaths |
| R63 |
KSatisfiability |
MaximumFixedLengthDisjointPaths |
| R64 |
HamiltonianCircuit |
QuadraticAssignment |
| R65 |
MinimumVertexCover |
MinimizingDummyActivitiesPERT |
| R66 |
ThreePartition |
IntersectionGraphSegmentsGrid |
| R67 |
ThreePartition |
EdgeEmbeddingOnGrid |
| R68 |
Planar3SAT |
GeometricConnectedDominatingSet |
| R69 |
ThreeDimensionalMatching |
MinimumBroadcastTime |
| R70 |
MinimumDominatingSet |
MinMaxMulticenter |
| R71 |
MinimumDominatingSet |
MinSumMulticenter |
Sets and Partitions Reductions (R72–R89)
| ID |
Source |
Target |
| R72 |
ExactCoverBy3Sets |
MaximumSetPacking |
| R73 |
NotAllEqual3SAT |
SetSplitting |
| R74 |
MinimumVertexCover |
SetBasis |
| R75 |
KColoring |
IntersectionPattern |
| R76 |
MinimumVertexCover |
ComparativeContainment |
| R77 |
ThreeDimensionalMatching |
ThreeMatroidIntersection |
| R78 |
Partition |
SubsetSum |
| R79 |
ExactCoverBy3Sets |
SubsetProduct |
| R80 |
ThreeDimensionalMatching |
ThreePartition |
| R81 |
ThreeDimensionalMatching |
Numerical3DimensionalMatching |
| R82 |
Numerical3DimensionalMatching |
NumericalMatchingTargetSums |
| R83 |
ExactCoverBy3Sets |
ExpectedComponentSum |
| R84 |
Partition |
MinimumSumOfSquares |
| R85 |
SubsetSum |
KthLargestSubset |
| R86 |
Partition |
KthLargestMTuple |
| R87 |
Partition |
BinPacking |
| R88 |
ThreePartition |
DynamicStorageAllocation |
| R89 |
ThreeDimensionalMatching |
PrunedTrieSpaceMinimization |
Storage and Retrieval Reductions (R098–R130)
| ID |
Source |
Target |
| R098 |
Partition |
ExpectedRetrievalCost |
| R099 |
RootedTreeArrangement |
RootedTreeStorageAssignment |
| R100 |
MinimumVertexCover |
MultipleCopyFileAllocation |
| R101 |
SubsetSum |
CapacityAssignment |
| R102 |
MinimumVertexCover |
ShortestCommonSupersequence |
| R103 |
MinimumVertexCover |
ShortestCommonSuperstring |
| R104 |
MinimumVertexCover |
LongestCommonSubsequence |
| R105 |
None |
BoundedPostCorrespondenceProblem |
| R106 |
KSatisfiability |
HittingString |
| R107 |
KColoring |
SparseMatrixCompression |
| R108 |
HamiltonianPath |
ConsecutiveOnesSubmatrix |
| R109 |
HamiltonianPath |
ConsecutiveOnesMatrixPartition |
| R110 |
OptimalLinearArrangement |
ConsecutiveOnesMatrixAugmentation |
| R111 |
HamiltonianPath |
ConsecutiveBlockMinimization |
| R112 |
HamiltonianPath |
ConsecutiveSets |
| R113 |
KColoring |
TwoDimensionalConsecutiveSets |
| R114 |
MinimumSetCovering |
StringToStringCorrection |
| R115 |
FeedbackEdgeSet |
GroupingBySwapping |
| R116 |
MinimumVertexCover |
ExternalMacroDataCompression |
| R117 |
MinimumVertexCover |
InternalMacroDataCompression |
| R118 |
ExactCoverBy3Sets |
RegularExpressionSubstitution |
| R119 |
KSatisfiability |
RectilinearPictureCompression |
| R120 |
MinimumVertexCover |
MinimumCardinalityKey |
| R121 |
HittingSet |
AdditionalKey |
| R122 |
MinimumCardinalityKey |
PrimeAttributeName |
| R123 |
HittingSet |
BoyceCoddNormalFormViolation |
| R124 |
KColoring |
ConjunctiveQueryFoldability |
| R125 |
MaximumClique |
ConjunctiveBooleanQuery |
| R126 |
KSatisfiability |
TableauEquivalence |
| R127 |
Monotone3SAT |
SerializabilityOfDatabaseHistories |
| R128 |
HittingSet |
SafetyOfDatabaseTransactionSystems |
| R129 |
KSatisfiability |
ConsistencyOfDatabaseFrequencyTables |
| R130 |
LBAAcceptance |
SafetyOfFileProtectionSystems |
Sequencing and Scheduling Reductions (R131–R151)
| ID |
Source |
Target |
| R131 |
ThreePartition |
SequencingWithReleaseTimesAndDeadlines |
| R132 |
MaximumClique |
SequencingToMinimizeTardyTasks |
| R133 |
Partition |
SequencingToMinimizeTardyTaskWeight |
| R134 |
OptimalLinearArrangement |
SequencingToMinimizeWeightedCompletionTime |
| R135 |
ThreePartition |
SequencingToMinimizeWeightedTardiness |
| R136 |
Partition |
SequencingWithDeadlinesAndSetupTimes |
| R137 |
RegisterSufficiency |
SequencingToMinimizeMaximumCumulativeCost |
| R138 |
KSatisfiability |
PrecedenceConstrainedScheduling |
| R139 |
ThreePartition |
ResourceConstrainedScheduling |
| R140 |
MinimumVertexCover |
SchedulingWithIndividualDeadlines |
| R141 |
KSatisfiability |
PreemptiveScheduling |
| R142 |
Partition |
SchedulingToMinimizeWeightedCompletionTime |
| R143 |
Partition |
OpenShopScheduling |
| R144 |
ThreePartition |
FlowShopScheduling |
| R145 |
DirectedHamiltonianPath |
NoWaitFlowShopScheduling |
| R146 |
Numerical3DimensionalMatching |
TwoProcessorFlowShopWithBoundedBuffer |
| R147 |
ThreePartition |
JobShopScheduling |
| R148 |
KSatisfiability |
TimetableDesign |
| R149 |
ExactCoverBy3Sets |
StaffScheduling |
| R150 |
Partition |
ProductionPlanning |
| R151 |
KSatisfiability |
DeadlockAvoidance |
Mathematical Programming Reductions (R152–R159)
| ID |
Source |
Target |
| R152 |
KSatisfiability |
IntegerProgramming |
| R153 |
Partition |
QuadraticProgramming |
| R154 |
KSatisfiability |
CostParametricLinearProgramming |
| R155 |
HamiltonianCircuit |
FeasibleBasisExtension |
| R156 |
ExactCoverBy3Sets |
MinimumWeightSolutionLinearEquations |
| R157 |
Maximum2Satisfiability |
OpenHemisphere |
| R158 |
ExactCoverBy3Sets |
KRelevancy |
| R159 |
HamiltonianCircuit |
TravelingSalesmanPolytopeNonAdjacency |
File Structure
references/Garey&Johnson/issues/
├── models/ # 204 problem definition issue templates
│ ├── P02_3dimensional_matching.md
│ ├── P06_hamiltonian_circuit.md
│ └── ...
└── reductions/ # 149 reduction rule issue templates
├── R02_3sat_3dm.md
├── R03_3dm_x3c.md
└── ...
Each file is a complete GitHub issue template with:
- Formal problem definition (INSTANCE + QUESTION for decision, objective for optimization)
- Variables and schema description
- Complexity class and known algorithms
- G&J page reference and appendix code
