NDLI: Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Yamaguchi, Yutaro
Copyright Year	2016
Abstract	Mader's disjoint ${\cal S}$-paths problem is a common generalization of non-bipartite matching and Menger's disjoint paths problems. Lovász [J. Combin. Theory Ser. B, 28 (1980), pp. 208--236]) proposed a polynomial-time algorithm for this problem through a reduction to matroid matching. A more direct reduction to the linear matroid parity problem was given later by Schrijver [Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003], which led to faster algorithms. As a generalization of Mader's problem, Chudnovsky et al. [Combinatorica, 26 (2006), pp. 521--532] introduced a framework of packing non-zero $A$-paths in group-labelled graphs and proved a min-max theorem. Chudnovsky, Cunningham, and Geelen [Combinatorica, 28 (2008), pp. 145--161] provided an efficient combinatorial algorithm for this generalized problem. On the other hand, Pap [Combinatorica, 27 (2007), pp. 247--251] introduced a framework of packing non-returning $A$-paths as a further generalization. In this paper, we discuss possible extensions of Schrijver's reduction technique and the algorithm of Chudnovsky, Cunningham, and Geelen [Combinatorica, 28 (2008), pp. 145--161] to another framework introduced by Pap [A Constructive Approach to Matching and Its Generalizations, Ph.D. thesis, Institute of Mathematics, Eötvös Loránd University, Budapest, Hungary, 2006], under the name of the subgroup model, which apparently generalizes but in fact is equivalent to packing nonreturning $A$-paths. Extracting combinatorial aspects of Schrijver's reduction, we introduce the concept of coherent representation and provide a necessary and sufficient condition for the groups in question to admit a reduction to the linear matroid parity problem with coherent representations. As a consequence, we give faster algorithms for important special cases of packing nonzero $A$-paths. In addition, it turns out that packing nonreturning $A$-paths admits such a reduction to the linear matroid parity problem if and only if the size of the input label set is at most four, which leads to its efficient solvability in this special case.
Sponsorship	Japan Society for the Promotion of Science
Starting Page	474
Ending Page	492
Page Count	19
File Format	PDF
ISSN	08954801
DOI	10.1137/130949877
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	30
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2016-03-15
Access Restriction	Subscribed
Subject Keyword	group-labelled graph Factorization, matching, partitioning, covering and packing Projective representations and multipliers Matroids, geometric lattices $A$-path Graphs and linear algebra linear matroid parity disjoint paths Graph algorithms Paths and cycles
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Matroids Induced by Packing Subgraphs

Matroid-Based Packing of Arborescences

On Disjoint Common Bases in Two Matroids

Making Bipartite Graphs DM-Irreducible

On Maximal Independent Arborescence Packing

Path Odd-Covers of Graphs

Designs from Matroids

Finding minimal Ferrers-esque graphs on path graphs ans cycle graphs via set cover

Finding minimal Ferrers-esque graphs on path graphs ans cycle graphs via set cover

Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity

Similar Documents

Matroids Induced by Packing Subgraphs

Matroid-Based Packing of Arborescences

On Disjoint Common Bases in Two Matroids

Making Bipartite Graphs DM-Irreducible

On Maximal Independent Arborescence Packing

Path Odd-Covers of Graphs

Designs from Matroids

Finding minimal Ferrers-esque graphs on path graphs ans cycle graphs via set cover

Finding minimal Ferrers-esque graphs on path graphs ans cycle graphs via set cover

Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity