Skip to content

Navigation Menu

Appearance settings

- AI CODE CREATION
  GitHub CopilotWrite better code with AI
  GitHub Copilot appDirect agents from issue to merge
  MCP Registry^NewIntegrate external tools
- DEVELOPER WORKFLOWS
  ActionsAutomate any workflow
  CodespacesInstant dev environments
  IssuesPlan and track work
  Code ReviewManage code changes
- APPLICATION SECURITY
  GitHub Advanced SecurityFind and fix vulnerabilities
  Code securitySecure your code as you build
  Secret protectionStop leaks before they start
- EXPLORE
  Why GitHub
  Documentation
  Blog
  Changelog
  Marketplace
View all features
- BY COMPANY SIZE
  Enterprises
  Small and medium teams
  Startups
  Nonprofits
- BY USE CASE
  App Modernization
  DevSecOps
  DevOps
  CI/CD
  View all use cases
- BY INDUSTRY
  Healthcare
  Financial services
  Manufacturing
  Government
  View all industries
View all solutions
- EXPLORE BY TOPIC
  AI
  Software Development
  DevOps
  Security
  View all topics
- EXPLORE BY TYPE
  Customer stories
  Events & webinars
  Ebooks & reports
  Business insights
  GitHub Skills
- SUPPORT & SERVICES
  Documentation
  Customer support
  Community forum
  Trust center
  Partners
View all resources
- COMMUNITY
  GitHub SponsorsFund open source developers
- PROGRAMS
  Security Lab
  Maintainer Community
  Accelerator
  GitHub Stars
  Archive Program
- REPOSITORIES
  Topics
  Trending
  Collections
- ENTERPRISE SOLUTIONS
  Enterprise platformAI-powered developer platform
- AVAILABLE ADD-ONS
  GitHub Advanced SecurityEnterprise-grade security features
  Copilot for BusinessEnterprise-grade AI features
  Premium SupportEnterprise-grade 24/7 support
Pricing

Search code, repositories, users, issues, pull requests...

Search

Clear

Search syntax tips

Provide feedback

We read every piece of feedback, and take your input very seriously.

Include my email address so I can be contacted

Saved searches

Use saved searches to filter your results more quickly

Name

Query

To see all available qualifiers, see our documentation.

Appearance settings

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Dismiss alert

CodingThrust / problem-reductions Public

Notifications You must be signed in to change notification settings
Fork 6
Star 33

Code
Issues 129
Pull requests
Discussions
Actions
Projects
Security and quality
Insights

Additional navigation options

Code
Issues
Pull requests
Discussions
Actions
Projects
Security and quality
Insights

Back to Milestones

Garey & Johnson

Open

No due date

•Last updated Jun 4, 2026

Implement problem models and reduction rules from Garey & Johnson's Computers and Intractability (1979). Tracked by #183.

77% complete

List view

Select all issues: List view

0 issues of 95 selected

Open
(95)
Closed
(319)

[Rule] Subset Sum to Capacity Assignment

GoodAn issue passed all checks.An issue passed all checks.

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#426 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] 3-Partition to Sequencing to Minimize Weighted Tardiness

GoodAn issue passed all checks.An issue passed all checks.

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#473 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] 3-Partition to Job-Shop Scheduling

GoodAn issue passed all checks.An issue passed all checks.

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#485 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] 3-Partition to Flow-Shop Scheduling

GoodAn issue passed all checks.An issue passed all checks.

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#482 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] Partition to Sequencing Within Intervals

GoodAn issue passed all checks.An issue passed all checks.

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#205 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 9, 2026

[Rule] PARTITION to SHORTEST WEIGHT-CONSTRAINED PATH

GoodAn issue passed all checks.An issue passed all checks.

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#360 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] Hamiltonian Path to Consecutive Ones Submatrix

GoodAn issue passed all checks.An issue passed all checks.

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#432 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Model] TwoProcessorFlowShopWithBoundedBuffer

modelA model problem to be implemented.A model problem to be implemented.

Status: Open.

#509 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Model] NoWaitFlowShopScheduling

modelA model problem to be implemented.A model problem to be implemented.

Status: Open.

#508 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] Numerical 3-Dimensional Matching to Two-Processor Flow-Shop with Bounded Buffer

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#484 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] Directed Hamiltonian Path to No-Wait Flow-Shop Scheduling

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#483 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

Garey & Johnson Extraction: 342 Problems + 335 Reductions Catalog

documentationImprovements or additions to documentationImprovements or additions to documentation

Status: Open.

#183 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 5, 2026

[Rule] Clique to Minimum Tardiness Sequencing

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#206 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 9, 2026

[Model] NetworkReliability

modelA model problem to be implemented.A model problem to be implemented.

Status: Open.

#235 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Rule] HAMILTONIAN PATH to KTH BEST SPANNING TREE

IncompleteReduction doesn't cover all source instances (Rule Check 5)Reduction doesn't cover all source instances (Rule Check 5)

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#236 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Model] NetworkSurvivability

modelA model problem to be implemented.A model problem to be implemented.

Status: Open.

#237 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Rule] HAMILTONIAN CIRCUIT to BOUNDED COMPONENT SPANNING FOREST

IncompleteReduction doesn't cover all source instances (Rule Check 5)Reduction doesn't cover all source instances (Rule Check 5)

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#238 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Rule] 3-SATISFIABILITY to MULTIPLE CHOICE BRANCHING

NeedsOriginalPaperIssue requires consulting the original paper (paywalled/unavailable)Issue requires consulting the original paper (paywalled/unavailable)

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#243 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Rule] VERTEX COVER to MINIMUM CUT INTO BOUNDED SETS

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#250 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Rule] STEINER TREE to NETWORK RELIABILITY

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#256 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Rule] VERTEX COVER to NETWORK SURVIVABILITY

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#257 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Rule] 3-SATISFIABILITY to CHINESE POSTMAN FOR MIXED GRAPHS

IncompleteReduction doesn't cover all source instances (Rule Check 5)Reduction doesn't cover all source instances (Rule Check 5)

NeedsOriginalPaperIssue requires consulting the original paper (paywalled/unavailable)Issue requires consulting the original paper (paywalled/unavailable)

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#260 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 10, 2026

[Rule] HAMILTONIAN PATH to K-th SHORTEST PATH

IncompleteReduction doesn't cover all source instances (Rule Check 5)Reduction doesn't cover all source instances (Rule Check 5)

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#361 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] EXACT COVER BY 3-SETS to MinimumEdgeCostFlow

IncompleteReduction doesn't cover all source instances (Rule Check 5)Reduction doesn't cover all source instances (Rule Check 5)

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#362 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

[Rule] 3SAT to PATH CONSTRAINED NETWORK FLOW

NeedsOriginalPaperIssue requires consulting the original paper (paywalled/unavailable)Issue requires consulting the original paper (paywalled/unavailable)

ruleA new reduction rule to be added.A new reduction rule to be added.

Status: Open.

#364 In CodingThrust/problem-reductions;

· isPANN opened

on Mar 11, 2026

Footer

© 2026 GitHub, Inc.

Footer navigation

Terms
Privacy
Security
Status
Community
Docs
Contact

You can’t perform that action at this time.