Problems hard for treewidth but easy for stable gonality
From MaRDI portal
Abstract: We show that some natural problems that are XNLP-hard (which implies W[t]-hardness for all t) when parameterized by pathwidth or treewidth, become FPT when parameterized by stable gonality, a novel graph parameter based on optimal maps from graphs to trees. The problems we consider are classical flow and orientation problems, such as Undirected Flow with Lower Bounds (which is strongly NP-complete, as shown by Itai), Minimum Maximum Outdegree (for which W[1]-hardness for treewidth was proven by Szeider), and capacitated optimization problems such as Capacitated (Red-Blue) Dominating Set (for which W[1]-hardness was proven by Dom, Lokshtanov, Saurabh and Villanger). Our hardness proofs (that beat existing results) use reduction to a recent XNLP-complete problem (Accepting Non-deterministic Checking Counter Machine). The new easy parameterized algorithms use a novel notion of weighted tree partition with an associated parameter that we call treebreadth, inspired by Seese's notion of tree-partite graphs, as well as techniques from dynamical programming and integer linear programming.
Cites work
- A combinatorial Li-Yau inequality and rational points on curves
- Algorithmic applications of tree-cut width
- Bin packing with fixed number of bins revisited
- Capacitated Domination and Covering: A Parameterized Perspective
- Complexity of secure sets
- Computing graph gonality is hard
- Defensive alliances in graphs of bounded treewidth
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Harmonic Morphisms and Hyperelliptic Graphs
- scientific article; zbMATH DE number 5917571 (Why is no real title available?)
- scientific article; zbMATH DE number 3917707 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- Network flows. Theory, algorithms, and applications.
- On the space and circuit complexity of parameterized problems: classes and completeness
- On tree-partition-width
- Parameterized algorithms
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Recognizing hyperelliptic graphs in polynomial time
- Reduction algorithms for graphs of small treewidth
- Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
- Stable gonality is computable
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The structure of graphs not admitting a fixed immersion
- Treewidth is a lower bound on graph gonality
- Two-Commodity Flow
Cited in
(10)- Defensive alliances in graphs
- Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
- The parameterised complexity of integer multicommodity flow
- Structural parameterizations of b-coloring
- XNLP-completeness for parameterized problems on graphs with a linear structure
- On the parameterized complexity of computing tree-partitions
- XNLP-hardness of parameterized problems on planar graphs
- XNLP-completeness for parameterized problems on graphs with a linear structure
- XALP-completeness of parameterized problems on planar graphs
- Upward and rectilinear planarity are W[1]-hard parameterized by treewidth
This page was built for publication: Problems hard for treewidth but easy for stable gonality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039413)
