A Note on an NP-Complete Problem,

Abstract

We show in this note that the problem of two-coloring a graph G = (V, E) with a distinguished vertex p and two distinguished subset A (p) and B (p) of V, such that there is a red connected subgraph containing A + p, and a blue connected subgraph containing B + p, is NP-Complete. We prove this by reduction of 3-satisfiability by constructing, for a given boolean expression in disjunctive normal form with three variables in each term, a graph G with a distinguished vertex D and two subsets a (D) and B (D) such that the expression is satisfiable if and only if the graph has a two-coloring with the desired monochromatic subtrees. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1979
Accession Number
ADA102232

Entities

People

  • J. L. Lewandowski

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Availability
  • Computer Science
  • Computers
  • Construction
  • Contracts
  • Illinois
  • Military Research
  • Orientation (Direction)
  • Polynomials
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.