Summary
Complete catalog of 342 problem models and 335 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/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 (342)
Chapter 3 — Core NP-Complete Problems (P01–P11)
| ID |
Name |
G&J Ref |
| P01 |
DirectedHamiltonianPath |
— |
| P02 |
HamiltonianPathBetweenTwoPoints |
— |
| P03 |
BoundedDegreeSpanningTree |
— |
| P04 |
MinimumEquivalentDigraph |
— |
| P05 |
SequencingWithinIntervals |
— |
| P06 |
MinimumTestCollection |
— |
| P07 |
MinimumTardinessSequencing |
— |
| P08 |
ExactCoverBy4Sets |
— |
| P09 |
Graph3Colorability |
— |
| P10 |
PartitionIntoPathsOfLength2 |
— |
| P11 |
StarFreeRegularExpressionInequivalence |
— |
Appendix A1 — Graph Theory (GT) (P12–P76)
| ID |
Name |
G&J Ref |
| P12 |
VertexCover |
GT1 |
| P13 |
DominatingSet |
GT2 |
| P14 |
DomaticNumber |
GT3 |
| P15 |
GraphKColorability(chromaticNumber) |
GT4 |
| P16 |
AchromaticNumber |
GT5 |
| P17 |
MonochromaticTriangle |
GT6 |
| P18 |
FeedbackVertexSet |
GT7 |
| P19 |
FeedbackArcSet |
GT8 |
| P20 |
PartialFeedbackEdgeSet |
GT9 |
| P21 |
MinimumMaximalMatching |
GT10 |
| P22 |
PartitionIntoTriangles |
GT11 |
| P23 |
PartitionIntoIsomorphicSubgraphs |
GT12 |
| P24 |
PartitionIntoHamiltonianSubgraphs |
GT13 |
| P25 |
PartitionIntoForests |
GT14 |
| P26 |
PartitionIntoCliques |
GT15 |
| P27 |
PartitionIntoPerfectMatchings |
GT16 |
| P28 |
CoveringByCliques |
GT17 |
| P29 |
CoveringByCompleteBipartiteSubgraphs |
GT18 |
| P30 |
Clique |
GT19 |
| P31 |
IndependentSet |
GT20 |
| P32 |
InducedSubgraphWithPropertyΠ(*) |
GT21 |
| P33 |
InducedConnectedSubgraphWithPropertyΠ(*) |
GT22 |
| P34 |
InducedPath |
GT23 |
| P35 |
BalancedCompleteBipartiteSubgraph |
GT24 |
| P36 |
BipartiteSubgraph |
GT25 |
| P37 |
DegreeBoundedConnectedSubgraph |
GT26 |
| P38 |
PlanarSubgraph |
GT27 |
| P39 |
EdgeSubgraph |
GT28 |
| P40 |
TransitiveSubgraph |
GT29 |
| P41 |
UniconnectedSubgraph |
GT30 |
| P42 |
MinimumKConnectedSubgraph |
GT31 |
| P43 |
CubicSubgraph |
GT32 |
| P44 |
MinimumEquivalentDigraph |
GT33 |
| P45 |
HamiltonianCompletion |
GT34 |
| P46 |
IntervalGraphCompletion |
GT35 |
| P47 |
PathGraphCompletion |
GT36 |
| P48 |
HamiltonianCircuit |
GT37 |
| P49 |
DirectedHamiltonianCircuit |
GT38 |
| P50 |
HamiltonianPath |
GT39 |
| P51 |
Bandwidth |
GT40 |
| P52 |
DirectedBandwidth |
GT41 |
| P53 |
OptimalLinearArrangement |
GT42 |
| P54 |
DirectedOptimalLinearArrangement |
GT43 |
| P55 |
MinimumCutLinearArrangement |
GT44 |
| P56 |
RootedTreeArrangement |
GT45 |
| P57 |
DirectedEliminationOrdering |
GT46 |
| P58 |
EliminationDegreeSequence |
GT47 |
| P59 |
SubgraphIsomorphism |
GT48 |
| P60 |
LargestCommonSubgraph |
GT49 |
| P61 |
MaximumSubgraphMatching |
GT50 |
| P62 |
GraphContractability |
GT51 |
| P63 |
GraphHomomorphism |
GT52 |
| P64 |
DigraphDMorphism |
GT53 |
| P65 |
PathWithForbiddenPairs |
GT54 |
| P66 |
MultipleChoiceMatching |
GT55 |
| P67 |
GraphGrundyNumbering |
GT56 |
| P68 |
Kernel |
GT57 |
| P69 |
KClosure |
GT58 |
| P70 |
IntersectionGraphBasis |
GT59 |
| P71 |
PathDistinguishers |
GT60 |
| P72 |
MetricDimension |
GT61 |
| P73 |
NesetrilRödlDimension |
GT62 |
| P74 |
ThresholdNumber |
GT63 |
| P75 |
OrientedDiameter |
GT64 |
| P76 |
WeightedDiameter |
GT65 |
Appendix A2 — Network Design (ND) (P77–P127)
| ID |
Name |
G&J Ref |
| P77 |
DegreeConstrainedSpanningTree |
ND1 |
| P78 |
MaximumLeafSpanningTree |
ND2 |
| P79 |
ShortestTotalPathLengthSpanningTree |
ND3 |
| P80 |
BoundedDiameterSpanningTree |
ND4 |
| P81 |
CapacitatedSpanningTree |
ND5 |
| P82 |
GeometricCapacitatedSpanningTree |
ND6 |
| P83 |
OptimumCommunicationSpanningTree |
ND7 |
| P84 |
IsomorphicSpanningTree |
ND8 |
| P85 |
KthBestSpanningTree |
ND9 |
| P86 |
BoundedComponentSpanningForest |
ND10 |
| P87 |
MultipleChoiceBranching |
ND11 |
| P88 |
SteinerTreeInGraphs |
ND12 |
| P89 |
GeometricSteinerTree |
ND13 |
| P90 |
GraphPartitioning |
ND14 |
| P91 |
AcyclicPartition |
ND15 |
| P92 |
MaxCut |
ND16 |
| P93 |
MinimumCutIntoBoundedSets |
ND17 |
| P94 |
BiconnectivityAugmentation |
ND18 |
| P95 |
StrongConnectivityAugmentation |
ND19 |
| P96 |
NetworkReliability |
ND20 |
| P97 |
NetworkSurvivability |
ND21 |
| P98 |
TravelingSalesman |
ND22 |
| P99 |
GeometricTravelingSalesman |
ND23 |
| P100 |
BottleneckTravelingSalesman |
ND24 |
| P101 |
ChinesePostmanForMixedGraphs |
ND25 |
| P102 |
StackerCrane |
ND26 |
| P103 |
RuralPostman |
ND27 |
| P104 |
LongestCircuit |
ND28 |
| P105 |
LongestPath |
ND29 |
| P106 |
ShortestWeightConstrainedPath |
ND30 |
| P107 |
K^thShortestPath |
ND31 |
| P108 |
MinimumEdgeCostFlow |
ND32 |
| P109 |
IntegralFlowWithMultipliers |
ND33 |
| P110 |
PathConstrainedNetworkFlow |
ND34 |
| P111 |
IntegralFlowWithHomologousArcs |
ND35 |
| P112 |
IntegralFlowWithBundles |
ND36 |
| P113 |
UndirectedFlowWithLowerBounds |
ND37 |
| P114 |
DirectedTwoCommodityIntegralFlow |
ND38 |
| P115 |
UndirectedTwoCommodityIntegralFlow |
ND39 |
| P116 |
DisjointConnectingPaths |
ND40 |
| P117 |
MaximumLengthBoundedDisjointPaths |
ND41 |
| P118 |
MaximumFixedLengthDisjointPaths |
ND42 |
| P119 |
QuadraticAssignmentProblem |
ND43 |
| P120 |
MinimizingDummyActivitiesInPertNetworks |
ND44 |
| P121 |
ConstrainedTriangulation |
ND45 |
| P122 |
IntersectionGraphForSegmentsOnAGrid |
ND46 |
| P123 |
EdgeEmbeddingOnAGrid |
ND47 |
| P124 |
GeometricConnectedDominatingSet |
ND48 |
| P125 |
MinimumBroadcastTime |
ND49 |
| P126 |
MinMaxMulticenter |
ND50 |
| P127 |
MinSumMulticenter |
ND51 |
Appendix A3 — Sets and Partitions (SP) (P128–P149)
| ID |
Name |
G&J Ref |
| P128 |
3DimensionalMatching(3dm) |
SP1 |
| P129 |
ExactCoverBy3Sets(x3c) |
SP2 |
| P130 |
SetPacking |
SP3 |
| P131 |
SetSplitting |
SP4 |
| P132 |
MinimumCover |
SP5 |
| P133 |
MinimumTestSet |
SP6 |
| P134 |
SetBasis |
SP7 |
| P135 |
HittingSet |
SP8 |
| P136 |
IntersectionPattern |
SP9 |
| P137 |
ComparativeContainment |
SP10 |
| P138 |
3MatroidIntersection |
SP11 |
| P139 |
Partition |
SP12 |
| P140 |
SubsetSum |
SP13 |
| P141 |
SubsetProduct |
SP14 |
| P142 |
3Partition |
SP15 |
| P143 |
Numerical3DimensionalMatching |
SP16 |
| P144 |
NumericalMatchingWithTargetSums |
SP17 |
| P145 |
ExpectedComponentSum |
SP18 |
| P146 |
MinimumSumOfSquares |
SP19 |
| P147 |
K^thLargestSubset |
SP20 |
| P148 |
K^thLargestMTuple |
SP21 |
| P149 |
BinPacking |
SR1 |
Appendix A4 — Storage and Retrieval (SR) (P150–P184)
| ID |
Name |
G&J Ref |
| P150 |
DynamicStorageAllocation |
SR2 |
| P151 |
PrunedTrieSpaceMinimization |
SR3 |
| P152 |
ExpectedRetrievalCost |
SR4 |
| P153 |
RootedTreeStorageAssignment |
SR5 |
| P154 |
MultipleCopyFileAllocation |
SR6 |
| P155 |
CapacityAssignment |
SR7 |
| P156 |
ShortestCommonSupersequence |
SR8 |
| P157 |
ShortestCommonSuperstring |
SR9 |
| P158 |
LongestCommonSubsequence |
SR10 |
| P159 |
BoundedPostCorrespondenceProblem |
SR11 |
| P160 |
HittingString |
SR12 |
| P161 |
SparseMatrixCompression |
SR13 |
| P162 |
ConsecutiveOnesSubmatrix |
SR14 |
| P163 |
ConsecutiveOnesMatrixPartition |
SR15 |
| P164 |
ConsecutiveOnesMatrixAugmentation |
SR16 |
| P165 |
ConsecutiveBlockMinimization |
SR17 |
| P166 |
ConsecutiveSets |
SR18 |
| P167 |
2DimensionalConsecutiveSets |
SR19 |
| P168 |
StringToStringCorrection |
SR20 |
| P169 |
GroupingBySwapping |
SR21 |
| P170 |
ExternalMacroDataCompression |
SR22 |
| P171 |
InternalMacroDataCompression |
SR23 |
| P172 |
RegularExpressionSubstitution |
SR24 |
| P173 |
RectilinearPictureCompression |
SR25 |
| P174 |
MinimumCardinalityKey |
SR26 |
| P175 |
AdditionalKey |
SR27 |
| P176 |
PrimeAttributeName |
SR28 |
| P177 |
BoyceCoddNormalFormViolation |
SR29 |
| P178 |
ConjunctiveQueryFoldability |
SR30 |
| P179 |
ConjunctiveBooleanQuery |
SR31 |
| P180 |
TableauEquivalence |
SR32 |
| P181 |
SerializabilityOfDatabaseHistories |
SR33 |
| P182 |
SafetyOfDatabaseTransactionSystems(*) |
SR34 |
| P183 |
ConsistencyOfDatabaseFrequencyTables |
SR35 |
| P184 |
SafetyOfFileProtectionSystems(*) |
SR36 |
Appendix A5 — Sequencing and Scheduling (SS) (P185–P206)
| ID |
Name |
G&J Ref |
| P185 |
SequencingWithReleaseTimesAndDeadlines |
SS1 |
| P186 |
SequencingToMinimizeTardyTasks |
SS2 |
| P187 |
SequencingToMinimizeTardyTaskWeight |
SS3 |
| P188 |
SequencingToMinimizeWeightedCompletionTime |
SS4 |
| P189 |
SequencingToMinimizeWeightedTardiness |
SS5 |
| P190 |
SequencingWithDeadlinesAndSetUpTimes |
SS6 |
| P191 |
SequencingToMinimizeMaximumCumulativeCost |
SS7 |
| P192 |
MultiprocessorScheduling |
SS8 |
| P193 |
PrecedenceConstrainedScheduling |
SS9 |
| P194 |
ResourceConstrainedScheduling |
SS10 |
| P195 |
SchedulingWithIndividualDeadlines |
SS11 |
| P196 |
PreemptiveScheduling |
SS12 |
| P197 |
SchedulingToMinimizeWeightedCompletionTime |
SS13 |
| P198 |
OpenShopScheduling |
SS14 |
| P199 |
FlowShopScheduling |
SS15 |
| P200 |
NoWaitFlowShopScheduling |
SS16 |
| P201 |
TwoProcessorFlowShopWithBoundedBuffer |
SS17 |
| P202 |
JobShopScheduling |
SS18 |
| P203 |
TimetableDesign |
SS19 |
| P204 |
StaffScheduling |
SS20 |
| P205 |
ProductionPlanning |
SS21 |
| P206 |
DeadlockAvoidance |
SS22 |
Appendix A6 — Mathematical Programming (MP) (P207–P219)
| ID |
Name |
G&J Ref |
| P207 |
IntegerProgramming |
MP1 |
| P208 |
QuadraticProgramming(*) |
MP2 |
| P209 |
CostParametricLinearProgramming |
MP3 |
| P210 |
FeasibleBasisExtension |
MP4 |
| P211 |
MinimumWeightSolutionToLinearEquations |
MP5 |
| P212 |
OpenHemisphere |
MP6 |
| P213 |
KRelevancy |
MP7 |
| P214 |
TravelingSalesmanPolytopeNonAdjacency |
MP8 |
| P215 |
Knapsack |
MP9 |
| P216 |
IntegerKnapsack |
MP10 |
| P217 |
ContinuousMultipleChoiceKnapsack |
MP11 |
| P218 |
PartiallyOrderedKnapsack |
MP12 |
| P219 |
ComparativeVectorInequalities |
MP13 |
Appendix A7 — Algebra and Number Theory (AN) (P220–P237)
| ID |
Name |
G&J Ref |
| P220 |
QuadraticCongruences |
AN1 |
| P221 |
SimultaneousIncongruences |
AN2 |
| P222 |
SimultaneousDivisibilityOfLinearPolynomials |
AN3 |
| P223 |
ComparativeDivisibility |
AN4 |
| P224 |
ExponentialExpressionDivisibility |
AN5 |
| P225 |
NonDivisibilityOfAProductPolynomial |
AN6 |
| P226 |
NonTrivialGreatestCommonDivisor |
AN7 |
| P227 |
QuadraticDiophantineEquations |
AN8 |
| P228 |
AlgebraicEquationsOverGf[2] |
AN9 |
| P229 |
RootOfModulus1 |
AN10 |
| P230 |
NumberOfRootsForAProductPolynomial |
AN11 |
| P231 |
PeriodicSolutionRecurrenceRelation |
AN12 |
| P232 |
PermanentEvaluation |
AN13 |
| P233 |
CosineProductIntegration |
AN14 |
| P234 |
EquilibriumPoint |
AN15 |
| P235 |
UnificationWithCommutativeOperators |
AN16 |
| P236 |
UnificationForFinitelyPresentedAlgebras |
AN17 |
| P237 |
IntegerExpressionMembership |
AN18 |
Appendix A8 — Games and Puzzles (GP) (P238–P252)
| ID |
Name |
G&J Ref |
| P238 |
GeneralizedHex |
GP1 |
| P239 |
GeneralizedGeography |
GP2 |
| P240 |
GeneralizedKayles |
GP3 |
| P241 |
SequentialTruthAssignment |
GP4 |
| P242 |
VariablePartitionTruthAssignment |
GP5 |
| P243 |
Sift |
GP6 |
| P244 |
AlternatingHittingSet |
GP7 |
| P245 |
AlternatingMaximumWeightedMatching |
GP8 |
| P246 |
Annihilation |
GP9 |
| P247 |
N×nCheckers |
GP10 |
| P248 |
N×nGo |
GP11 |
| P249 |
LeftRightHackenbushForRedwoodFurniture |
GP12 |
| P250 |
SquareTiling |
GP13 |
| P251 |
CrosswordPuzzleConstruction |
GP14 |
| P252 |
GeneralizedInstantInsanity |
GP15 |
Appendix A9 — Logic (LO) (P253–P271)
| ID |
Name |
G&J Ref |
| P253 |
Satisfiability |
LO1 |
| P254 |
3Satisfiability(3sat) |
LO2 |
| P255 |
NotAllEqual3sat |
LO3 |
| P256 |
OneInThree3sat |
LO4 |
| P257 |
Maximum2Satisfiability |
LO5 |
| P258 |
GeneralizedSatisfiability |
LO6 |
| P259 |
SatisfiabilityOfBooleanExpressions |
LO7 |
| P260 |
NonTautology |
LO8 |
| P261 |
MinimumDisjunctiveNormalForm |
LO9 |
| P262 |
TruthFunctionallyCompleteConnectives |
LO10 |
| P263 |
QuantifiedBooleanFormulas(qbf)(*) |
LO11 |
| P264 |
FirstOrderTheoryOfEquality(*) |
LO12 |
| P265 |
ModalLogicS5Satisfiability |
LO13 |
| P266 |
ModalLogicProvability(*) |
LO14 |
| P267 |
PredicateLogicWithoutNegation |
LO15 |
| P268 |
ConjunctiveSatisfiabilityWithFunctionsAndInequalities |
LO16 |
| P269 |
MinimumAxiomSet |
LO17 |
| P270 |
FirstOrderSubsumption |
LO18 |
| P271 |
SecondOrderInstantiation |
LO19 |
Appendix A10 — Automata and Language Theory (AL) (P272–P292)
| ID |
Name |
G&J Ref |
| P272 |
FiniteStateAutomatonInequivalence |
AL1 |
| P273 |
TwoWayFiniteStateAutomatonNonEmptiness |
AL2 |
| P274 |
LinearBoundedAutomatonAcceptance |
AL3 |
| P275 |
QuasiRealtimeAutomatonAcceptance |
AL4 |
| P276 |
NonErasingStackAutomatonAcceptance |
AL5 |
| P277 |
FiniteStateAutomataIntersection |
AL6 |
| P278 |
ReductionOfIncompletelySpecifiedAutomata |
AL7 |
| P279 |
MinimumInferredFiniteStateAutomaton |
AL8 |
| P280 |
RegularExpressionInequivalence |
AL9 |
| P281 |
MinimumInferredRegularExpression |
AL10 |
| P282 |
ReynoldsCoveringForContextFreeGrammars |
AL11 |
| P283 |
CoveringForLinearGrammars |
AL12 |
| P284 |
StructuralInequivalenceForLinearGrammars |
AL13 |
| P285 |
RegularGrammarInequivalence |
AL14 |
| P286 |
NonLr(k)ContextFreeGrammar |
AL15 |
| P287 |
EtolGrammarNonEmptiness |
AL16 |
| P288 |
ContextFreeProgrammedLanguageMembership |
AL17 |
| P289 |
QuasiRealTimeLanguageMembership |
AL18 |
| P290 |
EtolLanguageMembership |
AL19 |
| P291 |
ContextSensitiveLanguageMembership |
AL20 |
| P292 |
TreeTransducerLanguageMembership |
AL21 |
Appendix A11 — Program Optimization (PO) (P293–P312)
| ID |
Name |
G&J Ref |
| P293 |
RegisterSufficiency |
PO1 |
| P294 |
FeasibleRegisterAssignment |
PO2 |
| P295 |
RegisterSufficiencyForLoops |
PO3 |
| P296 |
CodeGenerationOnAOneRegisterMachine |
PO4 |
| P297 |
CodeGenerationWithUnlimitedRegisters |
PO5 |
| P298 |
CodeGenerationForParallelAssignments |
PO6 |
| P299 |
CodeGenerationWithAddressExpressions |
PO7 |
| P300 |
CodeGenerationWithUnfixedVariableLocations |
PO8 |
| P301 |
EnsembleComputation |
PO9 |
| P302 |
MicrocodeBitOptimization |
PO10 |
| P303 |
InequivalenceOfProgramsWithArrays |
PO11 |
| P304 |
InequivalenceOfProgramsWithAssignments |
PO12 |
| P305 |
InequivalenceOfFiniteMemoryPrograms(*) |
PO13 |
| P306 |
InequivalenceOfLoopProgramsWithoutNesting |
PO14 |
| P307 |
InequivalenceOfSimpleFunctions |
PO15 |
| P308 |
StrongInequivalenceOfIanovSchemes |
PO16 |
| P309 |
StrongInequivalenceForMonadicRecursionSchemes |
PO17 |
| P310 |
NonContainmentForFreeBSchemes |
PO18 |
| P311 |
NonFreedomForLoopFreeProgramSchemes |
PO19 |
| P312 |
ProgramsWithFormallyRecursiveProcedures |
PO20 |
Appendix A12 — Miscellaneous (MS) (P313–P331)
| ID |
Name |
G&J Ref |
| P313 |
Betweenness |
MS1 |
| P314 |
CyclicOrdering |
MS2 |
| P315 |
NonLivenessOfFreeChoicePetriNets |
MS3 |
| P316 |
ReachabilityFor1ConservativePetriNets(*) |
MS4 |
| P317 |
FiniteFunctionGeneration(*) |
MS5 |
| P318 |
PermutationGeneration |
MS6 |
| P319 |
DecodingOfLinearCodes |
MS7 |
| P320 |
ShapleyShubikVotingPower |
MS8 |
| P321 |
Clustering |
MS9 |
| P322 |
RandomizationTestForMatchedPairs(*) |
MS10 |
| P323 |
MaximumLikelihoodRanking |
MS11 |
| P324 |
MatrixDomination |
MS12 |
| P325 |
MatrixCover |
MS13 |
| P326 |
SimplyDeviatedDisjunction |
MS14 |
| P327 |
DecisionTree |
MS15 |
| P328 |
MinimumWeightAnd/orGraphSolution |
MS16 |
| P329 |
FaultDetectionInLogicCircuits |
MS17 |
| P330 |
FaultDetectionInDirectedGraphs |
MS18 |
| P331 |
FaultDetectionWithTestPoints |
MS19 |
Open Problems (P332–P342)
| ID |
Name |
G&J Ref |
| P332 |
GraphIsomorphism |
OPEN1 |
| P333 |
SubgraphHomeomorphism(forAFixedGraphH) |
OPEN2 |
| P334 |
GraphGenus |
OPEN3 |
| P335 |
ChordalGraphCompletion |
OPEN4 |
| P336 |
ChromaticIndex |
OPEN5 |
| P337 |
SpanningTreeParityProblem |
OPEN6 |
| P338 |
PartialOrderDimension |
OPEN7 |
| P339 |
PrecedenceConstrained3ProcessorScheduling |
OPEN8 |
| P340 |
LinearProgramming |
OPEN9 |
| P341 |
TotalUnimodularity |
OPEN10 |
| P342 |
CompositeNumber |
OPEN11 |
Reduction Rules (335)
Core Reductions — Chapter 3 (R01–R24)
| ID |
Source |
Target |
| R001 |
SATISFIABILITY (SAT) |
3-SATISFIABILITY (3SAT) |
| R002 |
3-SATISFIABILITY (3SAT) |
3-DIMENSIONAL MATCHING (3DM) |
| R003 |
3-DIMENSIONAL MATCHING (3DM) |
EXACT COVER BY 3-SETS (X3C) |
| R004 |
VERTEX COVER |
INDEPENDENT SET |
| R005 |
VERTEX COVER |
CLIQUE |
| R006 |
3-SATISFIABILITY (3SAT) |
VERTEX COVER |
| R007 |
VERTEX COVER |
HAMILTONIAN CIRCUIT |
| R008 |
HAMILTONIAN CIRCUIT |
HAMILTONIAN PATH |
| R009 |
HAMILTONIAN CIRCUIT (undirected) |
DIRECTED HAMILTONIAN CIRCUIT |
| R010 |
3-DIMENSIONAL MATCHING (3DM) |
PARTITION |
| R011 |
EXACT COVER BY 3-SETS (X3C) |
MINIMUM COVER |
| R012 |
VERTEX COVER |
HITTING SET |
| R013 |
CLIQUE |
SUBGRAPH ISOMORPHISM |
| R014 |
HAMILTONIAN PATH |
BOUNDED DEGREE SPANNING TREE |
| R015 |
Directed Hamiltonian Circuit |
Minimum Equivalent Digraph |
| R016 |
PARTITION |
KNAPSACK |
| R017 |
Partition |
Multiprocessor Scheduling |
| R018 |
Vertex Cover |
Ensemble Computation |
| R019 |
Exact Cover by 3-Sets |
Partition Into Triangles |
| R020 |
Partition |
Sequencing Within Intervals |
| R021 |
3-Dimensional Matching (3DM) |
Minimum Test Collection |
| R022 |
Clique |
Minimum Tardiness Sequencing |
| R023 |
VERTEX COVER |
FEEDBACK VERTEX SET |
| R024 |
VERTEX COVER |
FEEDBACK ARC SET |
Graph Theory Reductions (A1) (R25–R71)
| ID |
Source |
Target |
| R025 |
3SAT |
CLIQUE |
| R026 |
CLIQUE |
BALANCED COMPLETE BIPARTITE SUBGRAPH |
| R027 |
X3C |
GEOMETRIC CAPACITATED SPANNING TREE |
| R028 |
X3C |
OPTIMUM COMMUNICATION SPANNING TREE |
| R029 |
HAMILTONIAN PATH |
ISOMORPHIC SPANNING TREE |
| R030 |
HAMILTONIAN PATH |
KTH BEST SPANNING TREE |
| R031 |
HAMILTONIAN CIRCUIT |
BOUNDED COMPONENT SPANNING FOREST |
| R031 |
PARTITION INTO PATHS OF LENGTH 2 |
BOUNDED COMPONENT SPANNING FOREST |
| R032 |
3SAT |
MULTIPLE CHOICE BRANCHING |
| R033 |
X3C |
STEINER TREE IN GRAPHS |
| R033 |
X3C |
STEINER TREE IN GRAPHS |
| R034 |
X3C |
GEOMETRIC STEINER TREE |
| R035 |
MAX 2SAT |
GRAPH PARTITIONING |
| R035 |
PARTITION INTO TRIANGLES |
GRAPH PARTITIONING |
| R036 |
3SAT |
ACYCLIC PARTITION |
| R036 |
X3C |
ACYCLIC PARTITION |
| R037 |
MAX 2-SATISFIABILITY |
MAX CUT |
| R037 |
NAE3SAT |
MAX CUT |
| R038 |
SIMPLE MAX CUT |
MINIMUM CUT INTO BOUNDED SETS |
| R038 |
VERTEX COVER |
MINIMUM CUT INTO BOUNDED SETS |
| R039 |
HAMILTONIAN CIRCUIT |
BICONNECTIVITY AUGMENTATION |
| R040 |
HAMILTONIAN CIRCUIT |
STRONG CONNECTIVITY AUGMENTATION |
| R041 |
STEINER TREE IN GRAPHS |
NETWORK RELIABILITY |
| R042 |
VERTEX COVER |
NETWORK SURVIVABILITY |
| R043 |
HAMILTONIAN CIRCUIT |
TRAVELING SALESMAN |
| R044 |
X3C |
GEOMETRIC TRAVELING SALESMAN |
| R045 |
HAMILTONIAN CIRCUIT |
BOTTLENECK TRAVELING SALESMAN |
| R046 |
3SAT |
CHINESE POSTMAN FOR MIXED GRAPHS |
| R047 |
HAMILTONIAN CIRCUIT |
STACKER-CRANE |
| R048 |
HAMILTONIAN CIRCUIT |
RURAL POSTMAN |
| R049 |
HAMILTONIAN CIRCUIT |
LONGEST CIRCUIT |
| R050 |
HAMILTONIAN PATH BETWEEN TWO VERTICES |
LONGEST PATH |
| R051 |
PARTITION |
SHORTEST WEIGHT-CONSTRAINED PATH |
| R052 |
HAMILTONIAN PATH |
K-th SHORTEST PATH |
| R053 |
EXACT COVER BY 3-SETS |
MINIMUM EDGE-COST FLOW |
| R054 |
PARTITION |
INTEGRAL FLOW WITH MULTIPLIERS |
| R055 |
3SAT |
PATH CONSTRAINED NETWORK FLOW |
| R056 |
3SAT |
INTEGRAL FLOW WITH HOMOLOGOUS ARCS |
| R057 |
INDEPENDENT SET |
INTEGRAL FLOW WITH BUNDLES |
| R058 |
SATISFIABILITY |
UNDIRECTED FLOW WITH LOWER BOUNDS |
| R059 |
3SAT |
DIRECTED TWO-COMMODITY INTEGRAL FLOW |
| R060 |
DIRECTED TWO-COMMODITY INTEGRAL FLOW |
UNDIRECTED TWO-COMMODITY INTEGRAL FLOW |
| R061 |
3SAT |
DISJOINT CONNECTING PATHS |
| R062 |
3SAT |
MAXIMUM LENGTH-BOUNDED DISJOINT PATHS |
| R063 |
3SAT |
MAXIMUM FIXED-LENGTH DISJOINT PATHS |
| R064 |
HAMILTONIAN CIRCUIT |
QUADRATIC ASSIGNMENT PROBLEM |
| R065 |
VERTEX COVER |
MINIMIZING DUMMY ACTIVITIES IN PERT NETWORKS |
| R066 |
3-PARTITION |
INTERSECTION GRAPH FOR SEGMENTS ON A GRID |
| R067 |
3-PARTITION |
EDGE EMBEDDING ON A GRID |
| R068 |
PLANAR 3SAT |
GEOMETRIC CONNECTED DOMINATING SET |
| R069 |
3-DIMENSIONAL MATCHING |
MINIMUM BROADCAST TIME |
| R070 |
DOMINATING SET |
MIN-MAX MULTICENTER |
| R071 |
DOMINATING SET |
MIN-SUM MULTICENTER |
Sets and Partitions Reductions (A3) (R72–R89)
| ID |
Source |
Target |
| R072 |
EXACT COVER BY 3-SETS |
SET PACKING |
| R073 |
NOT-ALL-EQUAL 3SAT |
SET SPLITTING |
| R074 |
VERTEX COVER |
SET BASIS |
| R075 |
GRAPH 3-COLORABILITY |
INTERSECTION PATTERN |
| R076 |
VERTEX COVER |
COMPARATIVE CONTAINMENT |
| R077 |
3-DIMENSIONAL MATCHING |
3-MATROID INTERSECTION |
| R078 |
PARTITION |
SUBSET SUM |
| R079 |
EXACT COVER BY 3-SETS |
SUBSET PRODUCT |
| R080 |
3-DIMENSIONAL MATCHING |
3-PARTITION |
| R081 |
3-DIMENSIONAL MATCHING |
NUMERICAL 3-DIMENSIONAL MATCHING |
| R082 |
NUMERICAL 3-DIMENSIONAL MATCHING |
NUMERICAL MATCHING WITH TARGET SUMS |
| R083 |
EXACT COVER BY 3-SETS |
EXPECTED COMPONENT SUM |
| R084 |
PARTITION |
MINIMUM SUM OF SQUARES |
| R085 |
SUBSET SUM |
K-th LARGEST SUBSET |
| R086 |
PARTITION |
K-th LARGEST m-TUPLE |
| R087 |
PARTITION |
BIN PACKING |
| R088 |
3-PARTITION |
DYNAMIC STORAGE ALLOCATION |
| R089 |
3-DIMENSIONAL MATCHING |
PRUNED TRIE SPACE MINIMIZATION |
Storage and Retrieval Reductions (A4) (R90–R130)
| ID |
Source |
Target |
| R098 |
Partition / 3-Partition |
Expected Retrieval Cost |
| R099 |
Rooted Tree Arrangement |
Rooted Tree Storage Assignment |
| R100 |
Vertex Cover |
Multiple Copy File Allocation |
| R101 |
Subset Sum |
Capacity Assignment |
| R102 |
to |
? |
| R103 |
Vertex Cover (for cubic graphs) |
Shortest Common Superstring |
| R104 |
Vertex Cover |
Longest Common Subsequence |
| R105 |
to |
? |
| R106 |
3SAT |
Hitting String |
| R107 |
Graph 3-Colorability |
Sparse Matrix Compression |
| R108 |
Hamiltonian Path |
Consecutive Ones Submatrix |
| R109 |
Hamiltonian Path (for cubic graphs) |
Consecutive Ones Matrix Partition |
| R110 |
Optimal Linear Arrangement |
Consecutive Ones Matrix Augmentation |
| R111 |
Hamiltonian Path |
Consecutive Block Minimization |
| R112 |
Hamiltonian Path |
Consecutive Sets |
| R113 |
Graph 3-Colorability |
2-Dimensional Consecutive Sets |
| R114 |
Set Covering |
String-to-String Correction |
| R115 |
Feedback Edge Set |
Grouping by Swapping |
| R116 |
Vertex Cover |
External Macro Data Compression |
| R117 |
Vertex Cover |
Internal Macro Data Compression |
| R118 |
X3C |
Regular Expression Substitution |
| R119 |
3SAT |
Rectilinear Picture Compression |
| R120 |
Vertex Cover |
Minimum Cardinality Key |
| R121 |
Hitting Set |
Additional Key |
| R122 |
Minimum Cardinality Key |
Prime Attribute Name |
| R123 |
Hitting Set |
Boyce-Codd Normal Form Violation |
| R124 |
Graph 3-Colorability |
Conjunctive Query Foldability |
| R125 |
Clique |
Conjunctive Boolean Query |
| R126 |
3SAT |
Tableau Equivalence |
| R127 |
Monotone 3SAT |
Serializability of Database Histories |
| R128 |
Hitting Set |
Safety of Database Transaction Systems |
| R129 |
3SAT |
Consistency of Database Frequency Tables |
| R130 |
Linear Bounded Automaton Acceptance |
Safety of File Protection Systems |
Sequencing and Scheduling Reductions (A5) (R131–R151)
| ID |
Source |
Target |
| R131 |
3-Partition |
Sequencing with Release Times and Deadlines |
| R132 |
Clique |
Sequencing to Minimize Tardy Tasks |
| R133 |
Partition |
Sequencing to Minimize Tardy Task Weight |
| R134 |
Optimal Linear Arrangement |
Sequencing to Minimize Weighted Completion Time |
| R135 |
3-Partition |
Sequencing to Minimize Weighted Tardiness |
| R136 |
Partition |
Sequencing with Deadlines and Set-Up Times |
| R137 |
Register Sufficiency |
Sequencing to Minimize Maximum Cumulative Cost |
| R138 |
3SAT |
Precedence Constrained Scheduling |
| R139 |
3-Partition |
Resource Constrained Scheduling |
| R140 |
Vertex Cover |
Scheduling with Individual Deadlines |
| R141 |
3SAT |
Preemptive Scheduling |
| R142 |
Partition |
Scheduling to Minimize Weighted Completion Time |
| R143 |
Partition |
Open-Shop Scheduling |
| R144 |
3-Partition |
Flow-Shop Scheduling |
| R145 |
Directed Hamiltonian Path |
No-Wait Flow-Shop Scheduling |
| R146 |
Numerical 3-Dimensional Matching |
Two-Processor Flow-Shop with Bounded Buffer |
| R147 |
3-Partition |
Job-Shop Scheduling |
| R148 |
3SAT |
Timetable Design |
| R149 |
X3C |
Staff Scheduling |
| R150 |
Partition |
Production Planning |
| R151 |
3SAT |
Deadlock Avoidance |
Mathematical Programming Reductions (A6) (R152–R163)
| ID |
Source |
Target |
| R152 |
3SAT |
Integer Programming |
| R153 |
Partition |
Quadratic Programming |
| R154 |
3SAT |
Cost-Parametric Linear Programming |
| R155 |
Hamiltonian Circuit |
Feasible Basis Extension |
| R156 |
X3C |
Minimum Weight Solution to Linear Equations |
| R157 |
Maximum 2-Satisfiability |
Open Hemisphere |
| R158 |
X3C |
K-Relevancy |
| R159 |
Hamiltonian Circuit |
Traveling Salesman Polytope Non-Adjacency |
| R160 |
SUBSET SUM |
INTEGER KNAPSACK |
| R161 |
PARTITION |
CONTINUOUS MULTIPLE CHOICE KNAPSACK |
| R162 |
CLIQUE |
PARTIALLY ORDERED KNAPSACK |
| R163 |
COMPARATIVE CONTAINMENT (with equal weights) |
COMPARATIVE VECTOR INEQUALITIES |
Algebra and Number Theory Reductions (A7) (R164–R181)
| ID |
Source |
Target |
| R164 |
3SAT |
QUADRATIC CONGRUENCES |
| R165 |
3SAT |
SIMULTANEOUS INCONGRUENCES |
| R166 |
QUADRATIC DIOPHANTINE EQUATIONS |
SIMULTANEOUS DIVISIBILITY OF LINEAR POLYNOMIALS |
| R167 |
3SAT |
COMPARATIVE DIVISIBILITY |
| R168 |
3SAT |
EXPONENTIAL EXPRESSION DIVISIBILITY |
| R169 |
3SAT |
NON-DIVISIBILITY OF A PRODUCT POLYNOMIAL |
| R170 |
3SAT |
NON-TRIVIAL GREATEST COMMON DIVISOR |
| R171 |
3SAT |
QUADRATIC DIOPHANTINE EQUATIONS |
| R172 |
X3C |
ALGEBRAIC EQUATIONS OVER GF[2] |
| R173 |
3SAT |
ROOT OF MODULUS 1 |
| R174 |
3SAT |
NUMBER OF ROOTS FOR A PRODUCT POLYNOMIAL |
| R175 |
3SAT |
PERIODIC SOLUTION RECURRENCE RELATION |
| R176 |
3SAT |
PERMANENT EVALUATION |
| R177 |
PARTITION |
COSINE PRODUCT INTEGRATION |
| R178 |
3SAT |
EQUILIBRIUM POINT |
| R179 |
3SAT |
UNIFICATION WITH COMMUTATIVE OPERATORS |
| R180 |
3SAT |
UNIFICATION FOR FINITELY PRESENTED ALGEBRAS |
| R181 |
SUBSET SUM |
INTEGER EXPRESSION MEMBERSHIP |
Games and Puzzles Reductions (A8) (R182–R196)
| ID |
Source |
Target |
| R182 |
QBF |
GENERALIZED HEX |
| R183 |
QBF |
GENERALIZED GEOGRAPHY |
| R184 |
QBF |
GENERALIZED KAYLES |
| R185 |
QBF |
SEQUENTIAL TRUTH ASSIGNMENT |
| R186 |
QBF |
VARIABLE PARTITION TRUTH ASSIGNMENT |
| R187 |
QBF |
SIFT |
| R188 |
QBF |
ALTERNATING HITTING SET |
| R189 |
QBF |
ALTERNATING MAXIMUM WEIGHTED MATCHING |
| R190 |
VERTEX COVER |
ANNIHILATION |
| R191 |
PLANAR GEOGRAPHY |
NxN CHECKERS |
| R192 |
PLANAR GEOGRAPHY |
NxN GO |
| R193 |
SET COVERING |
LEFT-RIGHT HACKENBUSH FOR REDWOOD FURNITURE |
| R194 |
DIRECTED HAMILTONIAN PATH |
SQUARE-TILING |
| R195 |
X3C |
CROSSWORD PUZZLE CONSTRUCTION |
| R196 |
EXACT COVER |
GENERALIZED INSTANT INSANITY |
Logic Reductions (A9) (R197–R215)
| ID |
Source |
Target |
| R197 |
(generic transformation) |
SATISFIABILITY |
| R198 |
SATISFIABILITY |
3-SATISFIABILITY |
| R199 |
3SAT |
NOT-ALL-EQUAL 3SAT |
| R200 |
3SAT |
ONE-IN-THREE 3SAT |
| R201 |
3SAT |
MAXIMUM 2-SATISFIABILITY |
| R202 |
3SAT |
GENERALIZED SATISFIABILITY |
| R203 |
(generic transformation) |
SATISFIABILITY OF BOOLEAN EXPRESSIONS |
| R204 |
SATISFIABILITY |
NON-TAUTOLOGY |
| R205 |
MINIMUM COVER |
MINIMUM DISJUNCTIVE NORMAL FORM |
| R206 |
3SAT |
TRUTH-FUNCTIONALLY COMPLETE CONNECTIVES |
| R207 |
(generic transformation) |
QUANTIFIED BOOLEAN FORMULAS (QBF) |
| R208 |
(generic transformation) |
FIRST ORDER THEORY OF EQUALITY |
| R209 |
3SAT |
MODAL LOGIC S5-SATISFIABILITY |
| R210 |
QBF |
MODAL LOGIC PROVABILITY |
| R211 |
3SAT |
PREDICATE LOGIC WITHOUT NEGATION |
| R212 |
3SAT |
CONJUNCTIVE SATISFIABILITY WITH FUNCTIONS AND INEQUALITIES |
| R213 |
X3C |
MINIMUM AXIOM SET |
| R214 |
3SAT |
FIRST ORDER SUBSUMPTION |
| R215 |
3SAT |
SECOND ORDER INSTANTIATION |
Automata and Language Theory Reductions (A10) (R216–R224)
| ID |
Source |
Target |
| R216 |
REGULAR EXPRESSION NON-UNIVERSALITY |
FINITE STATE AUTOMATON INEQUIVALENCE |
| R217 |
LINEAR BOUNDED AUTOMATON ACCEPTANCE |
TWO-WAY FINITE STATE AUTOMATON NON-EMPTINESS |
| R218 |
(generic transformation) |
LINEAR BOUNDED AUTOMATON ACCEPTANCE |
| R219 |
(generic transformation) |
QUASI-REALTIME AUTOMATON ACCEPTANCE |
| R220 |
LINEAR BOUNDED AUTOMATON ACCEPTANCE |
NON-ERASING STACK AUTOMATON ACCEPTANCE |
| R221 |
LINEAR SPACE ACCEPTANCE |
FINITE STATE AUTOMATA INTERSECTION |
| R224 |
3SAT |
REGULAR EXPRESSION INEQUIVALENCE |
Program Optimization Reductions — Part 1 (A11) (R225–R228)
| ID |
Source |
Target |
| R225 |
3SAT |
REGISTER SUFFICIENCY |
| R226 |
permutation generation |
REGISTER SUFFICIENCY FOR LOOPS |
Graph Theory Reductions — Appendix Supplement (A1) (R229–R284)
| ID |
Source |
Target |
| R229 |
SET SPLITTING |
BETWEENNESS |
| R230 |
3DM |
METRIC DIMENSION |
| R231 |
3DM |
PARTITION INTO ISOMORPHIC SUBGRAPHS |
| R232 |
3-PARTITION |
BANDWIDTH |
| R233 |
3-PARTITION |
DIRECTED BANDWIDTH |
| R234 |
3-PARTITION |
WEIGHTED DIAMETER |
| R235 |
3SAT |
DIRECTED ELIMINATION ORDERING |
| R236 |
3SAT |
DOMATIC NUMBER |
| R237 |
VERTEX COVER |
DOMINATING SET |
| R238 |
3SAT |
EDGE-SUBGRAPH |
| R239 |
3SAT |
GRAPH CONTRACTABILITY |
| R240 |
3SAT |
GRAPH GRUNDY NUMBERING |
| R241 |
3SAT |
GRAPH K-COLORABILITY |
| R242 |
3SAT |
INDUCED CONNECTED SUBGRAPH WITH PROPERTY Π (*) |
| R243 |
3SAT |
INDUCED PATH |
| R244 |
3SAT |
INDUCED SUBGRAPH WITH PROPERTY Π (*) |
| R245 |
3SAT |
KERNEL |
| R246 |
3SAT |
MONOCHROMATIC TRIANGLE |
| R247 |
3SAT |
MULTIPLE CHOICE MATCHING |
| R248 |
3SAT |
PARTITION INTO HAMILTONIAN SUBGRAPHS |
| R249 |
3SAT |
PATH WITH FORBIDDEN PAIRS |
| R250 |
BIPARTITE SUBGRAPH |
TRANSITIVE SUBGRAPH |
| R251 |
CLIQUE |
K-CLOSURE |
| R252 |
CLIQUE |
LARGEST COMMON SUBGRAPH |
| R253 |
CLIQUE |
MAXIMUM SUBGRAPH MATCHING |
| R254 |
COVERING BY CLIQUES |
INTERSECTION GRAPH BASIS |
| R255 |
EXACT COVER BY 3-SETS |
ELIMINATION DEGREE SEQUENCE |
| R256 |
GRAPH 3-COLORABILITY |
CUBIC SUBGRAPH |
| R257 |
GRAPH 3-COLORABILITY |
NESETRIL-RÖDL DIMENSION |
| R258 |
GRAPH 3-COLORABILITY |
PARTITION INTO FORESTS |
| R259 |
GRAPH GRUNDY NUMBERING |
DIGRAPH D-MORPHISM |
| R260 |
GRAPH K-COLORABILITY |
GRAPH HOMOMORPHISM |
| R261 |
GRAPH K-COLORABILITY |
PARTITION INTO CLIQUES |
| R262 |
HAMILTONIAN CIRCUIT |
HAMILTONIAN COMPLETION |
| R263 |
HAMILTONIAN CIRCUIT |
MINIMUM K-CONNECTED SUBGRAPH |
| R264 |
HAMILTONIAN PATH |
DEGREE-BOUNDED CONNECTED SUBGRAPH |
| R265 |
HAMILTONIAN PATH |
PLANAR SUBGRAPH |
| R266 |
INDEPENDENT SET restricted |
triangle free graphs to THRESHOLD NUMBER |
| R267 |
INTERVAL GRAPH COMPLETION |
PATH GRAPH COMPLETION |
| R268 |
MAXIMUM 2-SATISFIABILITY |
BIPARTITE SUBGRAPH |
| R269 |
MINIMUM MAXIMAL MATCHING |
ACHROMATIC NUMBER |
| R270 |
NOT-ALL-EQUAL 3SAT |
PARTITION INTO PERFECT MATCHINGS |
| R271 |
OPTIMAL LINEAR ARRANGEMENT |
DIRECTED OPTIMAL LINEAR ARRANGEMENT |
| R272 |
OPTIMAL LINEAR ARRANGEMENT |
INTERVAL GRAPH COMPLETION |
| R273 |
OPTIMAL LINEAR ARRANGEMENT |
ROOTED TREE ARRANGEMENT |
| R274 |
PARTITION INTO CLIQUES |
COVERING BY CLIQUES |
| R275 |
PARTITION INTO CLIQUES |
COVERING BY COMPLETE BIPARTITE SUBGRAPHS |
| R276 |
SET SPLITTING |
ORIENTED DIAMETER |
| R277 |
SIMPLE MAX CUT |
MINIMUM CUT LINEAR ARRANGEMENT |
| R278 |
SIMPLE MAX CUT |
OPTIMAL LINEAR ARRANGEMENT |
| R279 |
VERTEX COVER |
DIRECTED HAMILTONIAN CIRCUIT |
| R280 |
VERTEX COVER |
HAMILTONIAN PATH |
| R281 |
VERTEX COVER |
MINIMUM MAXIMAL MATCHING |
| R282 |
VERTEX COVER |
PARTIAL FEEDBACK EDGE SET |
| R283 |
VERTEX COVER |
PATH DISTINGUISHERS |
| R284 |
VERTEX COVER |
UNICONNECTED SUBGRAPH |
Network Design Reductions — Appendix Supplement (A2) (R285–R292)
| ID |
Source |
Target |
| R285 |
3SAT |
CAPACITATED SPANNING TREE |
| R286 |
DOMINATING SET |
MAXIMUM LEAF SPANNING TREE |
| R287 |
generic |
CONSTRAINED TRIANGULATION |
| R288 |
HAMILTONIAN PATH |
DEGREE CONSTRAINED SPANNING TREE |
| R289 |
HAMILTONIAN PATH |
ISOMORPHIC SPANNING TREE |
| R290 |
EXACT COVER BY 3-SETS |
BOUNDED DIAMETER SPANNING TREE |
| R291 |
X3C |
OPTIMUM COMMUNICATION SPANNING TREE |
| R292 |
EXACT COVER BY 3-SETS |
SHORTEST TOTAL PATH LENGTH SPANNING TREE |
Automata and Language Theory Reductions — Supplement (A10) (R293–R306)
| ID |
Source |
Target |
| R293 |
3SAT |
CONTEXT-FREE PROGRAMMED LANGUAGE MEMBERSHIP |
| R294 |
3SAT |
ETOL LANGUAGE MEMBERSHIP |
| R295 |
3SAT |
MINIMUM INFERRED REGULAR EXPRESSION |
| R296 |
3SAT |
QUASI-REAL-TIME LANGUAGE MEMBERSHIP |
| R297 |
3SAT |
REYNOLDS COVERING FOR CONTEXT-FREE GRAMMARS |
| R298 |
FINITE STATE AUTOMATON INEQUIVALENCE |
REGULAR GRAMMAR INEQUIVALENCE |
| R299 |
generic |
NON-LR(K) CONTEXT-FREE GRAMMAR |
| R300 |
generic |
TREE TRANSDUCER LANGUAGE MEMBERSHIP |
| R301 |
GRAPH 3-COLORABILITY |
REDUCTION OF INCOMPLETELY SPECIFIED AUTOMATA |
| R302 |
LINEAR BOUNDED AUTOMATON ACCEPTANCE |
CONTEXT-SENSITIVE LANGUAGE MEMBERSHIP |
| R303 |
MONOTONE 3SAT |
MINIMUM INFERRED FINITE STATE AUTOMATON |
| R304 |
REGULAR EXPRESSION NON-UNIVERSALITY |
COVERING FOR LINEAR GRAMMARS |
| R305 |
REGULAR EXPRESSION NON-UNIVERSALITY |
ETOL GRAMMAR NON-EMPTINESS |
| R306 |
REGULAR EXPRESSION NON-UNIVERSALITY |
STRUCTURAL INEQUIVALENCE FOR LINEAR GRAMMARS |
Program Optimization Reductions — Part 2 (A11) (R307–R323)
| ID |
Source |
Target |
| R307 |
3DM |
MICROCODE BIT OPTIMIZATION |
| R308 |
3SAT |
CODE GENERATION ON A ONE-REGISTER MACHINE |
| R309 |
3SAT |
CODE GENERATION WITH ADDRESS EXPRESSIONS |
| R310 |
3SAT |
CODE GENERATION WITH UNFIXED VARIABLE LOCATIONS |
| R311 |
3SAT |
FEASIBLE REGISTER ASSIGNMENT |
| R312 |
3SAT |
INEQUIVALENCE OF LOOP PROGRAMS WITHOUT NESTING |
| R313 |
3SAT |
INEQUIVALENCE OF PROGRAMS WITH ARRAYS |
| R314 |
3SAT |
INEQUIVALENCE OF PROGRAMS WITH ASSIGNMENTS |
| R315 |
3SAT |
NON-CONTAINMENT FOR FREE B-SCHEMES |
| R316 |
3SAT |
NON-FREEDOM FOR LOOP-FREE PROGRAM SCHEMES |
| R317 |
3SAT |
PROGRAMS WITH FORMALLY RECURSIVE PROCEDURES |
| R318 |
3SAT |
STRONG INEQUIVALENCE OF IANOV SCHEMES |
| R319 |
FEEDBACK VERTEX SET |
CODE GENERATION FOR PARALLEL ASSIGNMENTS |
| R320 |
FEEDBACK VERTEX SET |
CODE GENERATION WITH UNLIMITED REGISTERS |
| R321 |
INEQUIVALENCE OF LOOP PROGRAMS WITHOUT NESTING |
INEQUIVALENCE OF SIMPLE FUNCTIONS |
| R322 |
LINEAR BOUNDED AUTOMATON ACCEPTANCE |
INEQUIVALENCE OF FINITE MEMORY PROGRAMS |
| R323 |
STRONG INEQUIVALENCE OF IANOV SCHEMES |
STRONG INEQUIVALENCE FOR MONADIC RECURSION SCHEMES |
Miscellaneous Reductions (A12) (R324–R341)
| ID |
Source |
Target |
| R324 |
3DM |
DECODING OF LINEAR CODES |
| R325 |
3SAT |
CYCLIC ORDERING |
| R326 |
3SAT |
FAULT DETECTION IN LOGIC CIRCUITS |
| R327 |
3SAT |
NON-LIVENESS OF FREE CHOICE PETRI NETS |
| R328 |
FEEDBACK ARC SET |
MAXIMUM LIKELIHOOD RANKING |
| R329 |
FINITE STATE AUTOMATA INTERSECTION |
FINITE FUNCTION GENERATION |
| R330 |
GRAPH 3-COLORABILITY |
CLUSTERING |
| R331 |
LINEAR BOUNDED AUTOMATON ACCEPTANCE |
REACHABILITY FOR 1-CONSERVATIVE PETRI NETS |
| R332 |
MAX CUT |
MATRIX COVER |
| R333 |
MAX CUT |
SIMPLY DEVIATED DISJUNCTION |
| R334 |
MINIMUM MAXIMAL MATCHING |
MATRIX DOMINATION |
| R335 |
PARTITION |
RANDOMIZATION TEST FOR MATCHED PAIRS |
| R336 |
PARTITION |
SHAPLEY-SHUBIK VOTING POWER |
| R337 |
X3C |
DECISION TREE |
| R338 |
X3C |
FAULT DETECTION IN DIRECTED GRAPHS |
| R339 |
X3C |
FAULT DETECTION WITH TEST POINTS |
| R340 |
X3C |
MINIMUM WEIGHT AND/OR GRAPH SOLUTION |
| R341 |
X3C |
PERMUTATION GENERATION |
Notes
Duplicate R-Numbers
Some R-numbers have multiple files representing alternative reduction paths:
| R# |
Variant A |
Variant B |
| R31 |
HC → BoundedComponentSpanningForest |
PartitionIntoPathsOfLength2 → BoundedComponentSpanningForest |
| R33 |
X3C → SteinerTree (duplicate file) |
X3C → SteinerTreeInGraphs |
| R35 |
Max2SAT → GraphPartitioning |
PartitionIntoTriangles → GraphPartitioning |
| R36 |
3SAT → AcyclicPartition |
X3C → AcyclicPartition |
| R37 |
Max2SAT → MaxCut |
NAE3SAT → MaxCut |
| R38 |
SimpleMaxCut → MinCutBoundedSets |
VC → MinimumCutIntoBoundedSets |
Missing R-Numbers
R90–R97, R222–R223, R227–R228 have no corresponding files.
Complexity Classes
-
Most problems are NP-complete
-
Entries marked (*) are PSPACE-complete or harder
-
Open Problems (P332–P342) had unknown complexity status as of 1979
File Structure
references/issues/
├── models/ # 342 problem definition issue templates
│ ├── P1_directed_hamiltonian_path.md
│ ├── P2_hamiltonian_path_between_two_points.md
│ └── ... P342_composite_number.md
└── rules/ # 335 reduction rule issue templates
├── R01_sat_3sat.md
├── R02_3sat_3dm.md
└── ... R341_x3c_permutationgeneration.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
