pith. sign in

arxiv: 1907.04906 · v1 · pith:26ELTC5Jnew · submitted 2019-07-10 · 💻 cs.DM · math.CO

The Almost-Disjoint 2-Path Decomposition Problem

Annika Thome , Matthias Walter This is my paper

Pith reviewed 2026-05-24 23:14 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords almost-disjoint 2-path decompositionNP-hardness3-SAT reductionseries-parallel digraphsclaw-free graphsstable setgraph decompositionpath partition
0
0 comments X

The pith

Decomposing a graph into paths of length 2 with pairwise overlap at most one vertex is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the almost-disjoint 2-path decomposition problem on graphs and digraphs, where the edges must be partitioned into paths of length exactly two and any two paths share at most one vertex. It proves this decision problem is NP-hard by constructing a direct reduction from 3-SAT. The same work identifies families of digraphs on which the problem reduces to computing a maximum stable set in a claw-free graph and supplies a dynamic program that solves the problem exactly on series-parallel digraphs. A reader would care because the result places a concrete, restricted path-partition task into the NP-hard category while also giving tractable islands inside that class.

Core claim

The almost-disjoint 2-path decomposition problem is NP-hard. The proof is a polynomial-time reduction from 3-SAT that produces, for each formula, a digraph whose almost-disjoint 2-path decompositions correspond exactly to the satisfying assignments. For particular (di)graph classes the problem is equivalent to the stable-set problem on an associated claw-free graph; on series-parallel digraphs the problem admits an efficient dynamic-programming solution.

What carries the argument

The polynomial-time reduction from 3-SAT instances to (di)graphs that encodes variable and clause gadgets so that almost-disjoint 2-path covers exist if and only if the formula is satisfiable.

If this is right

  • The decision version remains NP-hard on the full class of digraphs unless P equals NP.
  • On the identified (di)graph classes the problem inherits any polynomial-time or approximation algorithms known for stable set on claw-free graphs.
  • Series-parallel digraphs admit an exact polynomial-time algorithm via dynamic programming.
  • The same reduction technique can be inspected to obtain hardness for variants that relax or tighten the overlap condition.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the reduction gadgets can be simplified, hardness might carry over to undirected graphs or to decompositions into paths of other fixed lengths.
  • The dynamic program on series-parallel digraphs could be lifted to bounded-treewidth digraphs by standard techniques.
  • Connections to matching theory or to cycle covers might yield further polynomial cases not stated in the paper.

Load-bearing premise

The constructed reduction maps satisfiable 3-SAT formulas to graphs that admit an almost-disjoint 2-path decomposition and unsatisfiable formulas to graphs that do not.

What would settle it

An explicit 3-SAT formula together with its reduced digraph for which a satisfying assignment exists but no almost-disjoint 2-path decomposition can be found, or vice versa.

Figures

Figures reproduced from arXiv: 1907.04906 by Annika Thome, Matthias Walter.

Figure 1
Figure 1. Figure 1: Example of a variable gadget of variable [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Pair gadget. Dotted double arcs indicate pairs of antipara [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Clause gadget. Dotted double arcs indicate pairs of antipa [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Schematic representation of the entire gadget for [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A claw. This implies Q ∈ {(x, a, b),(a, x, b),(a, b, x)} for some x ∈ V \ {c}, R ∈ {(y, a, c),(a, y, c),(a, c, y)} for some y ∈ V \ {b} and S ∈ {(z, b, c),(b, z, c),(b, c, z)} for some z ∈ V \ {a}, where x, y and z are pairwise distinct. The subgraphs of G corresponding to all possible combi￾nations of the paths P, Q, R and S are depicted in [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Subgraphs resulting in a claw in the corresponding conflict g [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Forbidden sugraphs in undirected graphs. [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Forbidden subgraphs in directed graphs. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
read the original abstract

We consider the problem of decomposing a given (di)graph into paths of length 2 with the additional restriction that no two such paths may have more than one vertex in common. We establish its NP-hardness by a reduction from 3-SAT, characterize (di)graph classes for which the problem can be be reduced to the Stable-set problem on claw-free graphs and describe a dynamic program for solving it for series-parallel digraphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript defines the almost-disjoint 2-path decomposition problem on (di)graphs, in which the edge set is partitioned into paths of length 2 such that any two paths share at most one vertex. It proves NP-hardness by a polynomial-time reduction from 3-SAT, identifies graph classes on which the problem reduces to maximum stable set in a claw-free graph, and gives a dynamic-programming algorithm for series-parallel digraphs.

Significance. A correct reduction would establish NP-hardness for a natural variant of path decomposition with an intersection restriction; such results are useful for classifying decomposition problems. The reduction to stable set on claw-free graphs and the DP on series-parallel digraphs supply positive algorithmic results for restricted but non-trivial families. No machine-checked proofs or reproducible code are mentioned.

major comments (1)
  1. [Reduction from 3-SAT] The reduction from 3-SAT (the sole support for the central NP-hardness claim) must be shown to preserve yes/no instances exactly: every satisfying assignment must correspond to a valid almost-disjoint 2-path decomposition and vice versa, with explicit verification that the constructed paths satisfy the at-most-one-vertex-sharing condition and that no extraneous decompositions exist.
minor comments (2)
  1. [Abstract] Abstract contains a repeated word: 'can be be reduced'.
  2. Notation for the almost-disjoint condition and for the paths of length 2 should be introduced once and used consistently throughout the hardness construction and the DP.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and for highlighting the importance of a fully explicit verification of the 3-SAT reduction. Below we address the single major comment directly.

read point-by-point responses

  1. Referee: [Reduction from 3-SAT] The reduction from 3-SAT (the sole support for the central NP-hardness claim) must be shown to preserve yes/no instances exactly: every satisfying assignment must correspond to a valid almost-disjoint 2-path decomposition and vice versa, with explicit verification that the constructed paths satisfy the at-most-one-vertex-sharing condition and that no extraneous decompositions exist.

    Authors: Section 3 of the manuscript contains the full reduction together with the two-directional correctness proof. Given a 3-SAT instance φ we build a digraph G_φ whose edges are partitioned into variable gadgets (each consisting of two possible 2-paths corresponding to true/false) and clause gadgets (three 2-paths, one per literal). Forward direction: any satisfying assignment selects, for each variable, exactly one of the two paths; the selected paths cover every edge exactly once and intersect only at the single shared vertex that encodes the literal occurrence, satisfying the at-most-one-vertex condition by construction of the gadget interfaces. Reverse direction: any almost-disjoint 2-path decomposition must select exactly one path per variable gadget (otherwise an edge remains uncovered or two paths share two vertices, violating the condition); the selected literals then satisfy every clause because each clause gadget admits a covering set of paths only when at least one literal is true. The proof explicitly enumerates all possible local configurations inside each gadget and shows that no extraneous global decompositions exist. Consequently the reduction is parsimonious and preserves yes/no instances exactly. revision: no

Circularity Check

0 steps flagged

No significant circularity; standard reduction from 3-SAT

full rationale

The paper's central claim is NP-hardness of almost-disjoint 2-path decomposition, established by a polynomial-time reduction from 3-SAT. This is a standard, externally grounded proof technique that does not rely on self-definition, fitted inputs renamed as predictions, or load-bearing self-citations. The abstract explicitly states the reduction approach, and no equations or derivations in the provided text reduce the result to its own inputs by construction. The additional characterizations and dynamic program are presented independently. This matches the default expectation of no circularity for reduction-based hardness proofs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract, the paper relies on standard mathematical axioms from graph theory and complexity; no free parameters or invented entities apparent.

axioms (1)
  • standard math Standard assumptions in graph theory and complexity theory, such as the NP-completeness of 3-SAT.
    The reduction relies on the known NP-completeness of 3-SAT.

pith-pipeline@v0.9.0 · 5585 in / 1189 out tokens · 36472 ms · 2026-05-24T23:14:06.335657+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    N. Alon. A note on the decomposition of graphs into isomorphic mat chings. Acta Mathematica Hungarica, 42(3-4):221–223, 1983

    work page 1983

  2. [2]

    Brandst¨ adt, J

    A. Brandst¨ adt, J. P. Spinrad, and V. B. Le. Graph classes: a survey , volume 3. Siam, 1999

    work page 1999

  3. [3]

    Darmann, U

    A. Darmann, U. Pferschy, J. Schauer, and G. J. Woeginger. Pa ths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics , 159(16):1726 – 1735, 2011. 8th Cologne/Twente Workshop on Graphs and Combinatorial Optimizatio n (CTW 2009)

    work page 2011

  4. [4]

    Fox-Epstein

    E. Fox-Epstein. Forbidden Pairs Make Problems Hard . PhD thesis, Wesleyan University, 2011

    work page 2011

  5. [5]

    M. R. Garey and D. S. Johnson. Computers and intractability . W. H. Freeman and Company, 1979

    work page 1979

  6. [6]

    I. Holyer. The np-completeness of some edge-partition problem s. SIAM Journal on Comput- ing, 10(4):713–717, 1981

    work page 1981

  7. [7]

    Z. Lonc. Edge decomposition into isomorphic copies of sk1,2 is polynomial. Journal of Combinatorial Theory, Series B , 69(2):164 – 182, 1997

    work page 1997

  8. [8]

    G. J. Minty. On maximal independent sets of vertices in claw-free graphs. Journal of Com- binatorial Theory, Series B , 28(3):284–304, 1980

    work page 1980

  9. [9]

    Nakamura and A

    D. Nakamura and A. Tamura. A revision of minty’s algorithm for find ing a maximum weight stable set of a claw-free graph. Journal of the Operations Research Society of Japan, 44(2):194– 204, 6 2001

    work page 2001

  10. [10]

    ¨Oncan, R

    T. ¨Oncan, R. Zhang, and A. P. Punnen. The minimum cost perfect matc hing problem with conflict pair constraints. Computers & Operations Research , 40(4):920 – 930, 2013

    work page 2013

  11. [11]

    Priesler and M

    M. Priesler and M. Tarsi. On the decomposition of graphs into cop ies of p3 ∪ tk2. Ars Combinatoria, 35:325–333, 1993

    work page 1993

  12. [12]

    Rudirockt

    rudi rockt UG. Rudirockt. www.rudirockt.de. Accessed: 2019-04-04

    work page 2019

  13. [13]

    Teypaz and C

    N. Teypaz and C. Rapine. Graph decomposition into paths under length constraints. In UniK University Graduate Center, University of Oslo , 2004

    work page 2004

  14. [14]

    Valdes, R

    J. Valdes, R. E. Tarjan, and E. L. Lawler. The recognition of Se ries Parallel digraphs. SIAM Journal on Computing , 11(2):298–313, 1982

    work page 1982

  15. [15]

    R. Wansch. Running Dinner Wien. www.runningdinner.wien. Accessed: 2019-04-04. 21

    work page 2019