Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915832877023232 |
|---|---|
| author | MIT Hardness Group Abel, Zachary Demaine, Erik D. Diomidova, Jenny Li, Jeffery Zhou, Zixiang |
| author_facet | MIT Hardness Group Abel, Zachary Demaine, Erik D. Diomidova, Jenny Li, Jeffery Zhou, Zixiang |
| contents | Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? This family of graph orientation problems is a special kind of SAT problem, where each variable (edge orientation) appears in exactly two clauses (vertex constraints) -- once positively and once negatively. We analyze the complexity of many natural vertex types (patterns of allowed vertex neighborhoods), most notably all sets of symmetric vertex types which depend on only the number of incoming edges. In many scenarios, including Planar and Non-Planar Symmetric Graph Orientation with constants, we give a full dichotomy characterizing P vs. NP-complete problem classes. We apply our results to obtain new polynomial-time algorithms, resolving a 20-year-old open problem about KPlumber; to simplify existing NP-hardness proofs for tiling with trominoes; and to prove new NP-completeness results for tiling with tetrominoes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_03488 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling MIT Hardness Group Abel, Zachary Demaine, Erik D. Diomidova, Jenny Li, Jeffery Zhou, Zixiang Computational Complexity Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? This family of graph orientation problems is a special kind of SAT problem, where each variable (edge orientation) appears in exactly two clauses (vertex constraints) -- once positively and once negatively. We analyze the complexity of many natural vertex types (patterns of allowed vertex neighborhoods), most notably all sets of symmetric vertex types which depend on only the number of incoming edges. In many scenarios, including Planar and Non-Planar Symmetric Graph Orientation with constants, we give a full dichotomy characterizing P vs. NP-complete problem classes. We apply our results to obtain new polynomial-time algorithms, resolving a 20-year-old open problem about KPlumber; to simplify existing NP-hardness proofs for tiling with trominoes; and to prove new NP-completeness results for tiling with tetrominoes. |
| title | Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2603.03488 |