NP-completeness conjecture for APUD(k,m) recognition
NP-completeness conjecture for APUD(k,m) recognition
For integers and , let denote the graph class consisting of intersection graphs of disks whose centers lie on parallel lines, with the relevant representation restricted by parameter .
APUD recognition conjecture. Recognition of is NP-complete.
The paper proves NP-completeness for the special case and asks whether the technique can establish NP membership for general . Thus the general recognition claim remains open in the source.
Sources & referencesView supporting material
Primary source
Onur Çağırıcı, “Computational Aspects of Problems on Visibility and Disk Graph Representations”, arXiv:2111.00609 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.