WorksComputer Science
Parameterised complexity of graph homomorphism to odd cycles
Abstract
A nonbipartite graph has an odd-cycle core precisely when it maps to its shortest odd cycle. Core recognition and homomorphism to an input odd cycle are both XNLP-complete for the width of a supplied path decomposition, XALP-complete for the width of a supplied tree decomposition, and W[SAT]-hard and in W[P] for feedback vertex number. Hardness persists on connected, 2-degenerate -vertex sources of girth for any fixed . Our reduction encodes lists by cycles sharing an edge. On inputs with an edge it increases treewidth and feedback vertex number by exactly two. Lean 4 checks this structural transfer. For feedback edge number , we compute the exact circular chromatic number in time up to polynomial factors, which gives the same upper bound for both decision problems.
Introduction
Does a nonbipartite graph map to its shortest odd cycle ? Gerards studied this question for graph homomorphisms [13]. It is also a recognition problem. The core of a finite graph is its smallest homomorphically equivalent subgraph, unique up to isomorphism. If , the inclusion gives equivalence, and is a core because every endomorphism of an odd cycle is an automorphism (Lemma 3). Conversely, if the core is for some odd , then gives an odd closed walk containing an odd cycle, so . Composing gives by the same argument in . Thus . Bipartite graphs have no odd-cycle core.
Theorem 1. Consider two decision problems on a finite simple undirected graph .
Does have an odd cycle as its core?
Given also an odd in binary, does ?
Each problem is XNLP-complete for the width of a supplied path decomposition, XALP-complete for the width of a supplied tree decomposition, and W[SAT]-hard and in W[P] for . All three hardness bounds hold on connected, 2-degenerate graphs of girth for every fixed .
Deleting edges leads to a different algorithm. If deleting edges leaves a forest, both problems are solvable in time up to polynomial factors. In fact we can compute the exact circular chromatic number within this bound (Theorem 15). For odd , the test is the circular-colouring threshold [21]. If is the odd girth of , inclusion of gives the reverse inequality. Core recognition therefore tests equality in this lower bound. Corollary 17 also gives polynomial time for both problems at girth .
The hardness proofs encode List Colouring in the geometry of an odd cycle. All reference cycles share an ordered edge . Its image determines the coordinates in every copy. A path from an input vertex to a forbidden coordinate then excludes exactly that colour. Each forbidden occurrence gets its own copy and path. Deleting , exposes a subdivision of the input graph with trees attached. Contracting selected paths instead gives the input graph joined to the edge . These two views of the same graph give matching upper and lower bounds.
Theorem 2. There is a polynomial-size, logspace reduction from List Colouring on a graph to , with odd and , such that
Supplied tree or path decompositions can be transformed within the same resource bounds. For every feedback vertex set of , the construction specifies a feedback vertex set of of size . If contains an edge, then the treewidth and feedback vertex number bounds are exact: and .
Theorem 1 also gives hardness for minimum width by forgetting the supplied decomposition. Amarilli asked whether bounding the treewidths of both input graphs makes homomorphism fixed-parameter tractable [2]. Here the target always has treewidth and pathwidth two. Since XNLP-hardness implies W[]-hardness for every fixed [4 Lemma 2], the reduction gives W[1]-hardness for the maximum of the two treewidths even on these targets.
Prior work and attribution. In May 2025 Amarilli reported workshop reductions indicating W[1]-hardness for the parameter [2]. Amarilli later clarified (personal communication) that the reduction from -Clique produces a homomorphism instance with source pathwidth and target pathwidth . Thus the workshop reduction already gives W[1]-hardness for source pathwidth with a target of pathwidth two. Our reduction from List Colouring takes to be an odd cycle and yields the completeness results for supplied decompositions in Theorem 1.
We use the XNLP-completeness of List Colouring for pathwidth [4 Theorem 15] and its XALP-completeness for treewidth [3 Theorem 8]. For feedback vertex number, Bodlaender, Groenland and Pilipczuk obtained W[3]-hardness for List Colouring and W[SAT]-hardness for Binary CSP [5 Table 1]. Their Binary CSP reduction certifies the truth of subformulas by propagating choices down a formula tree [6 Lemmas 11 and 14]. In Theorem 10 we express that propagation with colour lists and ordinary edges, strengthening the W[3] lower bound for List Colouring in [6 Corollary 34].
Piecyk and Rzążewski studied cutwidth and feedback vertex number for list homomorphism. Their conditional cutwidth bounds also apply to ordinary homomorphism for odd-cycle targets [19]. For each fixed odd cycle our reduction transfers algorithms in the opposite direction, from ordinary homomorphism to List Colouring with a fixed palette (Remark 13). Carbonnel gives single-exponential-time, polynomial-space algorithms measured in the number of source vertices for target families excluding a topological minor, together with improved randomised bounds for fixed odd-cycle targets [7 Theorems 1 and 2]. These bounds concern source order rather than the structural parameters studied here.
Disequality and list gadgets for projective cores are developed by Okrasa and Rzążewski [18 preprint version, Lemma 17 and Proposition 19]; their fixed-target width overhead may depend on the target. Kostochka, Nešetřil and Smolíková prove NP-completeness of fixed- colouring on 2-degenerate sources for nonbipartite triangle-free [15 Theorem 1.3]. Here the elimination of lists is uniform and polynomial-size, with additive structural overhead independent of the target length for all three parameters. The single-link reference copies provide the feedback vertex guarantee as well as connected sources of prescribed large girth.
Properties of odd cycles
Conventions. All graphs are finite, simple, and undirected. Path length counts edges. A tree decomposition consists of a nonempty tree and bags covering the graph’s vertices and edges, such that the bags containing any given vertex induce a connected subtree of . Its width is . A path decomposition has a path as its index tree. The parameters and are the minimum widths over tree and path decompositions, respectively. Thus the empty graph has width zero, witnessed by a single empty bag. A feedback vertex set is a set whose deletion leaves a forest, and denotes its minimum cardinality.
We identify with , with consecutive residues adjacent. Throughout this section is odd.
Lemma 3 (Rigidity). Every homomorphism has the form , where and . In particular, fixing the ordered edge fixes every vertex.
Proof. Choose the integer increment or for each of the consecutive steps of the image walk. Their sum is a multiple of , lies in , and is odd. It is therefore or , forcing all increments to have the same sign.
Lemma 4 (Inequality link). A path of length has a homomorphism to with endpoint images if and only if .
Proof. The possible integer displacements of a walk of that length are
These integers give distinct residues modulo : a difference is with , and is odd. None is zero modulo , since each is odd and has absolute value less than . Thus they give exactly the nonzero residues, and every listed displacement is realised by an appropriate sequence of forward and backward steps.
A link below means a path of length whose internal vertices are private. Different links may share endpoints, but no internal vertices.
The reduction
An instance of List Colouring consists of a graph and lists . It asks for a map with for every vertex and for every edge . Relabelling the palette is harmless. Choose the least odd integer , and regard the lists as subsets of .
Construct as follows.
Introduce a vertex for every and two further vertices , with edge .
For every pair , introduce a copy of , identifying its coordinates with , respectively. All other vertices of these cycles are private.
If , add a link from coordinate of to . This is the only link belonging to that reference copy.
For every edge , add one link from to .
There are no other edges. In particular, original edges of become links, not edges of . Copies with have no domain link; retaining these harmless copies makes the finite vertex type in Lean uniform.
In Figure 1, take and . The link from coordinate allows image at via the walk . It excludes image because has no closed walk of length three. The other domain links enforce the remaining exclusions, and the link between the hubs requires different colours.

Figure 1. Part of the construction for target . Solid edges form two reference cycles sharing . After normalising to , their private vertices have the indicated images. Each dashed link has three edges and two private internal vertices; it forces its endpoint images to differ. The remaining reference copies and domain links are omitted.
Lemma 5. The instance is list-colourable if and only if .
Proof. Given a homomorphism, compose it with a target automorphism to place at . By Lemma 3, every reference cycle then maps coordinatewise to . Lemma 4 says that the domain links exclude exactly the residues outside from the image of . The links corresponding to edges of force adjacent vertices to have different images. Thus is a list colouring. Conversely, given a list colouring, map each to its colour and every reference cycle coordinatewise. Each link has distinct endpoint images, so Lemma 4 extends the map over it. Private interiors make these extensions independent.
Treewidth
Deleting from exposes a subdivision of , trees attached at single hubs, and separate tree components. Subdivision preserves treewidth, and adding these trees raises it to at most , giving . Adding the two anchors yields . We give an explicit certificate construction so the same bound holds for supplied decompositions within the claimed resources.
Let contain the reference cycles, the hubs with the original edges of , and a direct edge from coordinate of to for every pair , including allowed colours. Root the private reference path at coordinate when , and at coordinate otherwise. Attach this root to , allowing an extra edge when needed. The resulting graph of hubs and private paths contains and is obtained from by attaching rooted trees at single vertices.
Keep the input bags. For each new vertex , add the bag below its parent’s bag, attaching a root bag to an input bag containing its hub. These are bags of size at most two. Add to every bag. The resulting decomposition of has width at most : old bags have size at most , and new bags have size at most four.
Delete unused direct domain edges and replace each required domain or original edge by its link. Subdivision uses bags of size three: for internal vertices , attach the chain at a bag containing . Vertex occurrences stay connected and all edges are covered. The width remains at most .
Pathwidth
Use the same auxiliary graph as in § 3.1. Its direct domain edges for allowed colours can only help provide a decomposition for the eventual source.
Given a path decomposition of of width , add to every bag. At the first bag containing , process all its reference cycles serially, retaining that enlarged bag. Traverse each reference cycle using a window of two consecutive private vertices. Every direct domain edge is covered when its reference vertex is in the window, since is retained. This gives a path decomposition of of width at most .
When the endpoints of an edge share a bag, subdividing that edge into an arbitrarily long path raises pathwidth by at most two: retain that bag and sweep the new path, with at most two consecutive internal vertices present at once. Process all subdivisions serially at their owning bags. Delete the unused direct domain edges and subdivide the required domain and original edges into links. Vertex intervals and edge coverage are preserved, giving . This conservative bound is the one formalised in Lean.
Feedback vertex sets
Let be a feedback vertex set of . Delete
from . The original-edge links form a subdivision of , together with pendant or detached path fragments from edges incident with . This is a forest. Every reference cycle minus is a path. Its single optional domain link attaches it to at most one surviving hub, or leaves pendant or detached fragments when an endpoint was deleted. Such attachments cannot create a cycle. Thus is a feedback vertex set and .
Exact parameter transfer
Proposition 6. For the padded construction, is a minor of , where the join adds two adjacent vertices adjacent to every vertex of . If contains an edge, then
For every nonempty , also .
Proof. Since , residue is forbidden at every hub. For each , take the copy and contract its entire private path and domain link into . Its edges to coordinates 0 and 1 become and . These private paths and link interiors are disjoint for distinct hubs. Retain , contract the original-edge links to edges, and discard the unused pieces. This produces without identifying hubs.
For nonempty , the standard join identity gives . Every chordal completion of the join restricts to one of , and every chordal completion of extends to the join; adjoining the two universal vertices increases the maximum clique size by two. Minor monotonicity supplies the lower bound, and the upper bound in § 3.1 matches it when has an edge.
Write , for its vertex cover number, and . Deleting both, exactly one, or neither of the two new vertices gives, respectively,
Indeed, with one new vertex surviving, the remaining vertices of must be independent; with both surviving, no vertex of may survive. When has an edge, : retain one vertex of a minimum vertex cover, leaving a star and isolated vertices after deleting the others. Also , by retaining the endpoints of an edge. Thus the displayed minimum is . Feedback vertex number is minor-monotone, so the existing upper bound is exact.
Finally, for nonempty . Indeed, restricting any path decomposition of the join to gives a bag with at least input vertices. Their occurrence intervals and those of the two universal vertices pairwise intersect. By the Helly property for intervals, some bag contains all these vertices, giving the lower bound. Adding the universal vertices to every input bag gives equality. Minor monotonicity and § 3.2 now give the bounds for . □
The minor argument uses a common missing colour, supplied by palette padding. The upper bounds also cover edgeless and empty inputs.
Size and construction resources
Write , , and . The exact source size is
Since , the output size is polynomial in the explicit input size. Here the palette may be taken to contain only colours occurring in the lists: order the distinct labels by first occurrence in the input and replace each by its rank. Repeated scans compute these ranks in logarithmic space, so is bounded by the input length even if the original labels are large binary integers.
Vertices and bags are named by a constant number of polynomially bounded indices. Each gadget is processed at the first input bag covering its attachment, found by rescanning the input. In the path construction the intermediate bag stream can likewise be regenerated on demand. Appendix § 6 gives the enumeration and its bag counts. The transducer uses logarithmic workspace and polynomial time, completing the proof of Theorem 2.
Sparse sources and large girth
Proposition 7. The source is 2-degenerate. If is nonempty, its girth is exactly .
Proof. Repeatedly remove internal vertices of links, all of which have degree at most two in the remaining graph. Then remove the private reference vertices, again of degree at most two. Only and isolated hubs remain. This gives a degeneracy ordering.
Before adding links, the nontrivial component consists of -cycles sharing only the edge ; its shortest cycle has length . Every link joins different components of this base graph, so a cycle using a link must use at least two links. Their private interiors force it to traverse each link in full, giving length at least . A reference cycle of length exists whenever has a vertex.
The choice gives a quantitative girth bound. By (1), for . Thus for every nonempty input the girth is at least . To impose any additional fixed lower bound on the girth, include it in the maximum defining . The target length remains polynomial in the input size, and all width and feedback bounds continue to hold.
The output is also connected. Since , residue is outside every input list. Each hub therefore has a domain link to the reference component containing . Every remaining vertex lies in a reference copy or a link. For empty , the output is simply . This explains the strict palette padding in the choice of .
Amplifying the girth by odd subdivision
Write for the graph obtained by replacing each edge of by a path of edges with private internal vertices. The following equivalence also follows from the circular-colouring theory of odd subdivisions [14]. We give an explicit projection because the reduction changes both the source and the target.
Lemma 8. For odd and positive odd ,
Proof. Given , send an original vertex of colour to in . Consecutive colours in give endpoints of a -edge arc in . Map each replacement path along this arc.
Conversely, define a map from the residues modulo to those modulo by writing an integer lift as , , and putting
Changing the lift by changes by . The endpoints of a -step walk have lifts at odd distance . Order these lifts increasingly. If they are in the same block of length , their remainders have opposite parities and their images differ by one. If they lie in successive blocks, their remainders differ by , which is even. Now the block indices differ by one, so again the images are adjacent. Applying to the images of the original vertices of proves the reverse implication.
Proposition 9. For every fixed , the reduction on nonempty inputs can output a connected, -degenerate graph of order and girth . Its shortest cycle has odd length equal to the new target length. Subdivision preserves the feedback vertex number and treewidth of the reduction graph and adds at most two to the width of its supplied path decomposition.
Proof. Let before subdivision. Fix an integer with , and set . Each cycle traverses its replacement paths in full, so subdivision multiplies every cycle length by . Proposition 7 thus gives girth , witnessed by an odd cycle. A -degenerate graph has at most edges, whence
The new graph is connected. Remove the new degree-two vertices first, then the original vertices, which are now isolated. This gives a 2-degeneracy ordering.
Every original feedback vertex set still hits every cycle. Conversely, replace each selected internal vertex by an endpoint of its original edge. Every original cycle lifts to a cycle and is hit by the resulting set. Contracting the replacement paths recovers as a minor. For the treewidth upper bound, attach a chain of bags of size three for each subdivided edge as in § 3.1. Here contains a cycle and hence has treewidth at least two. For pathwidth, retain the first bag containing the two endpoints and sweep the replacement paths assigned to that bag one at a time, keeping at most two internal vertices at once. For fixed , counters for edges, bags and positions along a path all use logarithmic space, and the output has polynomial length. Lemma 8 transfers the decision equivalence.
Complexity consequences
XNLP consists of problems decidable nondeterministically in time and space , where is the input length. XALP permits, in addition, an auxiliary stack with access only to its top; it has an equivalent characterisation by alternation with bounded total computation-tree size [4, 3]. We use parameterised logspace reductions, with workspace .
List Colouring with a feedback vertex set
Theorem 10. List Colouring is W[SAT]-hard parameterised by feedback vertex number, even when the input includes a set of vertices whose deletion leaves a tree and the parameter is .
Proof. Weighted Antimonotone Satisfiability asks whether an AND/OR formula with leaves , for in a set of variables, is satisfied by setting exactly variables true. It is W[SAT]-complete [1 Theorem 4.1(ii)]. Use its formula tree, with a separate vertex for every literal occurrence, including repeated occurrences of the same variable. For , output one vertex with an empty list and an empty deletion set. Henceforth assume .
Take the tree edges and add a clique of selectors, each with list . Join every literal vertex to every selector. A colouring of the clique chooses a set of exactly true variables. Assign the following active colours to the tree vertices.
an AND gate has one colour ;
an OR gate has a colour for each child ;
a leaf has colour .
All gate colours are distinct and disjoint from . The list at the root contains only its active colours. At every other vertex add one inactive colour, namely when its parent is an AND gate and when its parent is an OR gate.
Fix the selector colours. At a leaf , the active choice is available precisely when . On a tree edge from parent to child, the only colour shared by the two lists is the child’s inactive colour. Hence an active AND gate forces every child to be active, and an OR gate coloured forces child to be active. Induction from the leaves shows that every active vertex represents a true subformula. The root must be active, including when the formula consists of one literal.
Conversely, start at the root of a true formula. At a required AND gate use its active colour and require every child. At a required OR gate choose a true child, use its corresponding colour, and require that child alone. Colour each required leaf with and all unrequired vertices with their inactive colours. The required leaves avoid all selector colours; on each tree edge the parent uses the child’s inactive colour exactly when it requires that child. This gives a proper list colouring.
Deleting the selectors leaves the original formula tree. For a tree of nodes with leaves, the graph has vertices and edges. Gate colours can be named by their node and child indices. Given the formula as a node table with parent pointers, counters and input scans enumerate the lists and edges in logarithmic space. The supplied deletion set has size , so the minimum feedback vertex number is also bounded by the input weight. □
Transferring hardness to cycles. Apply Theorem 2 to the two published width lower bounds and to Theorem 10. The transformed decompositions have the claimed widths. The selector hubs and the two anchors give a supplied feedback set of size . We may adjoin a single isolated vertex with a singleton list to ensure a nonempty input, extending a supplied decomposition by a singleton bag. Proposition 9 gives the asserted girth restriction with the same feedback set and at most two more vertices per path bag. The resulting graph has a shortest cycle of odd length equal to the target length. By the equivalence in the introduction, discarding the target proves the same hardness for core recognition. These graphs have chromatic number three, by 2-degeneracy and the presence of an odd cycle.
Membership
We first bound the target length so that binary encoding does not increase the resources needed by the algorithms.
Lemma 11 (Capping the target length). Let and let be odd. If , then if and only if is bipartite. Setting preserves whether . The binary encoding of can be transformed to the unary encoding of in logarithmic space, leaving unchanged.
Proof. An odd closed walk of length in has an odd integer displacement that is a multiple of , so . A nonbipartite graph on vertices contains an odd cycle of length at most , precluding a homomorphism to when . Conversely, a bipartition maps to any edge of .
If the cap changes the target, both and exceed , so the preceding equivalence applies to both. The cap is odd and at least five. Scan the binary digits of with an accumulator saturated at ; then emit its value in unary. The counter uses bits and the output has symbols. Input validity, including oddness, can also be checked by scans. No source parameter or supplied decomposition changes. □
By Lemma 11, first replace a binary target length by its linear-size cap. In the membership arguments below, denotes this capped length, so target vertices have -bit identifiers and all loops over the target take polynomial time.
We first isolate the common correctness argument. A bag assignment is a map that preserves every graph edge with both endpoints in .
Lemma 12 (Gluing bag assignments). For a tree decomposition of , a homomorphism exists if and only if there are bag assignments that agree on for every edge of .
Proof. A homomorphism restricts to such assignments. Conversely, if a vertex occurs in two bags, every bag on the unique path between them also contains . Agreement across adjacent bags therefore gives a single image for , independent of the chosen occurrence. Vertex coverage defines this map on all of , and edge coverage makes it a homomorphism. □
Supplied width. On a path, guess one bag assignment at a time and check its internal edges and agreement with the preceding bag. On a rooted tree, visit children in depth-first order. Save the parent assignment, bag index and next-child index on the auxiliary stack before descending, then restore them on return. Every sibling thus sees the same parent assignment. Lemma 12 proves correctness in both cases. At most two assignments occupy the work tape, using bits for width and input length . Each bag and tree edge requires only polynomially many input scans. This gives XNLP membership on paths and XALP membership on trees. Appendix § 6 gives the preliminary logspace certificate check.
Feedback vertex number. A parameterised problem is in W[P] if a nondeterministic Turing machine decides it in time with at most nondeterministic steps [12 Chapter 3]. Let . Compute a minimum feedback vertex set deterministically in time [8]. Guess an image in for every vertex of , using nondeterministic bits, and reject unless the guess preserves the edges inside . The graph is a forest; root each of its trees. For a vertex of and a residue , call feasible if is adjacent in to the guessed image of every neighbour of in , and every child of has a feasible pair with adjacent to . Feasibility is computed from the leaves upwards in polynomial time, and the guess extends to a homomorphism exactly when every root has a feasible pair. This proves membership in W[P]. This membership result also follows from the Binary CSP upper bound [5 Theorem 2], since the standard encoding preserves the constraint graph. For both List Colouring and the input-cycle problem, the remaining feedback-number gap is between W[SAT]-hardness and W[P]-membership.
Core recognition. For the width algorithms, guess an odd and verify by guessing a closed walk of length in logarithmic space. Then check with the corresponding bag algorithm. For W[P], reject bipartite graphs and compute the odd girth deterministically in polynomial time before guessing the feedback-set images. The odd girth is the minimum distance between the two copies of any one vertex in the bipartite double cover, since this is the minimum length of an odd closed walk. This completes the proof of Theorem 1.
Remark 13 (Fixed target). For fixed odd , enumerating all assignments on a supplied feedback set of size takes time, where suppresses polynomial factors. Conversely, an algorithm for yields the same bound for List Colouring on colours. At the decision equivalence holds for arbitrary lists, and the supplied set grows by two, costing a factor for fixed . This transfer is unconditional.
Remark 14 (Forest targets). If a target forest has an edge, its sources are exactly the bipartite graphs. A nonempty edgeless target accepts precisely edgeless sources, and an empty target accepts only the empty source. Thus at target treewidth one the problem is polynomial-time decidable.
Circular colouring by feedback edge number
For , the circular clique has vertex set . Two colours are adjacent when their difference lies in the integer interval modulo . Thus is isomorphic to , since its two steps are and is coprime to . Write and , where is the number of connected components. This feedback edge number counts the edges outside a spanning forest.
Theorem 15. For positive given in binary with , deciding takes time and polynomial space, where is the input length. The exact circular chromatic number of can be computed within the same bounds.
Proof. On an oriented chain of edges, every step contributes an arbitrary integer in . The possible sums are all integers in
Indeed, start each step at and distribute any desired excess of at most among the steps. Reduction modulo gives exactly the feasible endpoint differences. In particular a component that is a cycle of length is feasible if and only if this interval contains a multiple of .
Repeatedly remove vertices of degree at most one. Any colouring extends back across these deletions, since every target colour has a neighbour. Test pure cycle components as above. In each other remaining component, suppress the maximal degree-two chains, retaining their lengths and any resulting loops or parallel edges. The multigraph has minimum degree three and its original feedback edge number . With vertices and edges it satisfies and , hence . Altogether there are at most chains.
For a chain directed from to , put and let represent mod . If every residue is possible. Otherwise, using representatives , the permitted integer differences form the nonempty intersections
For a loop the difference is zero. Enumerate one interval per constrained chain. Each chosen interval gives two difference constraints and . Express the coordinate bounds relative to a common variable, which may be translated to zero. A branch is feasible exactly when the constraint digraph has no negative cycle. In that case shortest distances from a new source of zero-weight arcs give integral coordinates. The chain criterion extends the endpoint colours independently across their private interiors. Conversely any colouring selects a feasible branch. The branches can be processed sequentially. All weights, including , have polynomial bit length.
For a graph with an edge, is the least feasible ratio . Vince’s finite-attainment theorem gives a minimiser with for connected graphs [20 Theorem 3]. For a disjoint union take the maximum over components, since circular colourability is monotone in the ratio [21]. Test the pairs with and and return the least feasible ratio by integer comparison. We use the usual chromatic conventions 1 for a nonempty edgeless graph and 0 for the empty graph.
The theorem includes homomorphism to an input odd cycle. For recognition, reject bipartite graphs and apply the threshold test at , , where is the odd girth.
Corollary 16. Computing and deciding both problems of Theorem 1 are fixed-parameter tractable for feedback vertex number plus maximum degree.
Proof. Deleting all edges incident with a minimum feedback vertex set leaves a forest. Thus , and Theorem 15 needs only the graph as input.
Corollary 17. On graphs of order and finite girth , computing and solving both problems of Theorem 1 take time. The running time is polynomial whenever .
Proof. Write . We first bound for every . Discard tree components, which contribute zero to . Put . In each remaining component take a maximal set of centres pairwise at distance greater than . The radius- balls about all centres are disjoint. Each contains at least vertices, since the component is connected and has at least vertices. Thus the total number of centres is at most .
Maximality puts every vertex within distance of a centre. Simultaneous breadth-first search from the centres partitions the graph into rooted trees of radius at most . Contract the tree edges. An extra edge internal to a tree would close a cycle of length at most . Two edges joining the same pair of trees would, with the paths in the two trees, form a cycle of length at most . Both lengths are less than . Hence the contraction gives a simple graph on vertices. Each tree-edge contraction preserves , so . Theorem 15 gives the first time bound.
To obtain the polynomial range, suppose . Then . Connect the original components by bridges, giving a simple graph of the same girth with edges. For , the girth bound of Bollobás and Szemerédi [10] gives . Since , we obtain . Theorem 15 now takes polynomial time, as it also does for .
The girth bound counts all cycles. For core recognition a companion algorithm [16] gives polynomial time already at odd girth , by using the odd girth as the target length. For an independently supplied target, its length can be much smaller than the source girth. The case of girth and unrestricted odd target length remains open in these bounds.
Encoding and checking decompositions
Emitting the graph. Let denote the length of the explicitly encoded input, including any supplied decomposition. Give output vertices identifiers consisting of a type tag and a constant number of indices: an original vertex, a residue, a reference position, or an original edge and a link position. All indices are polynomially bounded in , so an identifier occupies bits. Nested counters enumerate the vertices and edges. List membership and original adjacency are decided by rescanning the input; original edges are emitted once, in increasing endpoint order. If consecutive integer identifiers are required, the rank of a tuple can be recomputed by enumerating its predecessors. Output in binary; the corresponding cycle can also be enumerated explicitly. Neither an adjacency table nor a list of output vertices is stored.
Emitting a tree decomposition. Fix an order on the input bags. A reference gadget belongs to the first bag containing ; an original-edge link belongs to the first bag containing both endpoints. Such an owning bag exists by vertex or edge coverage and can be found by scans.
The reference-path root has coordinate . Its bag has parent the owning input bag; the bag at any other private coordinate has parent if , and if , within the same copy. Its vertex parent follows the same rule, except that the root’s vertex parent is . Emit the input bags with added, and the reference bags . These formulas require only coordinate comparisons and give the decomposition of directly.
A required direct domain edge belongs to its copy’s root bag when , and to its owning input bag when or . An original edge belongs to its owning input bag. Emit each subdivision chain of size-three bags from § 3.1 at that bag. Parents within a chain are consecutive indices, so both bags and decomposition edges can be emitted without a general forest traversal.
Emitting a path decomposition. Implement the two stages of § 3.2 in order. For each input bag, emit its enlargement by , followed by the reference windows for vertices whose first occurrence is that bag. Order these windows by vertex, residue, and reference position. This is an explicit stream of bags for . For each required link, find the first bag of this stream containing its endpoints by regenerating the stream. At that bag insert the link’s consecutive internal-vertex windows, retaining the whole bag of . Order links with the same owning bag by their identifiers. The intermediate stream need not be stored: its bags and their contents can be recomputed by counters and input scans.
If the input decomposition has bags, either construction uses output bags. Every bag is emitted one vertex at a time, and each owning-bag query stores only indices and membership flags. The enumerations have a fixed number of nested loops over polynomially bounded ranges. Consequently the transducer uses workspace, polynomial time, and polynomial output length, independently of the input width.
Checking the certificate. The algorithms do not assume valid decompositions as a promise. We encode a tree by a designated root and one parent pointer for every other bag. Reject out-of-range pointers and require every bag to reach the root within steps, where is the number of bags. This checks that the index graph is a tree using counters and rescans.
For each graph vertex , count its occurrence bags, say , and the tree edges with both endpoints among those bags, say . The induced index subgraph is a forest, so it is nonempty and connected exactly when and . Thus these counts check vertex coverage and connected occurrences. Bag entries, duplicate entries, bag sizes, and coverage of each graph edge are checked by scans. For a path, check that every occurrence set is a nonempty interval. These preliminary checks take logarithmic workspace and polynomial time. No decomposition-finding algorithm is assumed.
Lean verification
The artifact uses Lean 4.35.0 [11] and mathlib v4.35.0 [17]. It checks the weighted-formula and List Colouring decision reductions, the supplied decomposition and feedback-set transfers, their numerical bounds and matching lower bounds, and the connection with odd-cycle cores. It also checks the original source girth and size bounds, the endpoint projection for odd subdivision, and the walk interval for an odd-cycle target. The circular-clique generalisation, graph-level girth amplification, encodings and running times are proved in the manuscript.
To reproduce the audit at revision 848545a, run python3 scripts/check_formalization.py from the repository root [9]. It builds the library, checks for proof admissions and audits the principal declarations. FORMALIZATION.md indexes the statements and the README gives commands for the finite checks. Mathematical development, formalisation and drafting used AI assistance under human direction.
References
- [1]K. A. Abrahamson, R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic 73(3):235–276, 1995. doi:10.1016/0168-0072(94)00034-Z.DOI
- [2]Antoine Amarilli. Complexity of the homomorphism problem parameterized by treewidth. Theoretical Computer Science Stack Exchange, question 34877, June 2, 2016, with a comment on workshop reductions, May 30, 2025. https://cstheory.stackexchange.com/q/34877.
- [3]Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk and Michał Pilipczuk. On the complexity of problems on tree-structured graphs. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), LIPIcs, vol. 249, pp. 6:1–6:17. Schloss Dagstuhl, 2022. doi:10.4230/LIPIcs.IPEC.2022.6.DOI
- [4]Hans L. Bodlaender, Carla Groenland, Jesper Nederlof and Céline Swennenhuis. Parameterized problems complete for nondeterministic FPT time and logarithmic space. Information and Computation 300:105195, 2024. doi:10.1016/j.ic.2024.105195.DOI
- [5]Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk. Parameterized complexity of Binary CSP: vertex cover, treedepth, and related parameters. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), LIPIcs, vol. 261, pp. 27:1–27:20. Schloss Dagstuhl, 2023. doi:10.4230/LIPIcs.ICALP.2023.27.arxiv.org/abs/2208.12543
- [6]Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk. Parameterized complexity of Binary CSP: vertex cover, treedepth, and related parameters. Full version, arXiv:2208.12543v5, 2023.arxiv.org/abs/2208.12543
- [7]Clément Carbonnel. Faster algorithms for graph homomorphism via tractable constraint satisfaction. arXiv:2602.23000v2, 2026.arxiv.org/abs/2602.23000
- [8]Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.DOI
- [9]Jason Davies. Odd-cycle homomorphism: Lean formalisation and executable checks. Software repository, 2026. Version 848545a. https://github.com/jasondavies/odd-cycle-homomorphism.
- [10]Béla Bollobás and Endre Szemerédi. Girth of sparse graphs. Journal of Graph Theory 39(3):194–200, 2002. doi:10.1002/jgt.10023.DOI
- [11]Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction – CADE 28, LNCS, vol. 12699, pp. 625–635. Springer, 2021. doi:10.1007/978-3-030-79876-5_37.DOI
- [12]Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, 2006. doi:10.1007/3-540-29953-X.DOI
- [13]A. M. H. Gerards. Homomorphisms of graphs into odd cycles. Journal of Graph Theory 12(1):73–83, 1988. doi:10.1002/jgt.3190120108.DOI
- [14]Hossein Hajiabolhassan and Ali Taherkhani. On the circular chromatic number of graph powers. Journal of Graph Theory 75(1):48–58, 2014. doi:10.1002/jgt.21722.DOI
- [15]A. Kostochka, J. Nešetřil and P. Smolíková. Colorings and homomorphisms of degenerate and bounded degree graphs. Discrete Mathematics 233:257–276, 2001. doi:10.1016/S0012-365X(00)00245-4.DOI
- [16]Jason Davies. Homomorphisms to long odd cycles in time exponential in the order-to-length ratio. Companion manuscript, 2026. Distributed alongside this paper as long-odd-cycles.pdf.
- [17]The mathlib Community. The Lean mathematical library. In Certified Programs and Proofs (CPP 2020), pp. 367–381. ACM, 2020. doi:10.1145/3372885.3373824.DOI
- [18]Karolina Okrasa and Paweł Rzążewski. Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs. SIAM Journal on Computing 50(2):487–508, 2021. doi:10.1137/20M1320146. Preprint version: arXiv:1906.08371v3, 2020.DOI
- [19]Marta Piecyk and Paweł Rzążewski. Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), LIPIcs, vol. 187, pp. 56:1–56:17. Schloss Dagstuhl, 2021. doi:10.4230/LIPIcs.STACS.2021.56.
- [20]Andrew Vince. Star chromatic number. Journal of Graph Theory 12(4):551–559, 1988. doi:10.1002/jgt.3190120411.DOI
- [21]Xuding Zhu. Circular chromatic number: a survey. Discrete Mathematics 229(1–3):371–410, 2001. doi:10.1016/S0012-365X(00)00217-X.DOI