|
This paper investigates vertex-ordering problems in loop-free directed graphs with constraints on the left-going arcs, focusing on the existence of vertex orderings in which these arcs form subgraphs with specific structures. For example, we prove that determining whether there exists an ordering such that the left-going arcs form an in-branching can be solved in polynomial time, while the analogous problem for matchings is NP-complete. As a generalization, we introduce the $(f,g;\sum w)$-bounded ordering problem, which incorporates vertex-specific lower and upper bounds on the $w$-weighted left-degree. We explore the relationship between vertex-ordering problems and their arc-partitioning variants, where the goal is to partition the graph into a subgraph with specific structure and an acyclic subgraph. We show that for certain graph families such as in-branchings, disjoint paths, and matchings, the two problems are equivalent, while for others, like in-arborescences and perfect matchings, they diverge. Our comprehensive complexity analysis covers various special cases and modified constraints, revealing a rich landscape of computational complexity. These results advance the understanding of ordered digraphs and their computational boundaries, with implications for graph degeneracy, acyclic orientations, influence propagation and rank aggregation.
Bibtex entry:
| AUTHOR | = | {Borsik A., N{\'o}ra and Madarasi, P{\'e}ter}, |
| TITLE | = | {Vertex-ordering and arc-partitioning problems}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2024}, |
| NUMBER | = | {TR-2024-19} |