NDLI: Half-integrality, LP-branching, and FPT Algorithms

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Iwata, Yoichi Yoshida, Yuichi Wahlström, Magnus
Copyright Year	2016
Abstract	A recent trend in parameterized algorithms is the application of polytope tools to fixed-parameter tractable (FPT) algorithms [e.g., Cygan et al., FOCS 2011, 52nd Annual Symposium on Foundations of Computer Science, IEEE, 2011, pp. 150--159; Narayanaswamy et al., STACS 2012, Symposium on Theoretical Aspects of Computer Science, 2012, pp. 338--349]. Although this approach has yielded significant speedups for a range of important problems, it requires the underlying polytope to have very restrictive properties, including half-integrality and Nemhauser--Trotter-style persistence properties. To date, these properties are essentially known to hold only for two classes of polytopes, covering the cases of Vertex Cover [Nemhauser and Trotter, Math. Program., 8 (1975), pp. 232--248] and Node Multiway Cut [Garg et al., J. Alg., 50 (2004), pp. 49--61]. Taking a slightly different approach, we view half-integrality as a discrete relaxation of a problem, e.g., a relaxation of the search space from $\{0,1\}^V$ to $\{0,1/2,1\}^V$ such that the new problem admits a polynomial-time exact solution. Using tools from constraint satisfaction problems [in particular Thapper and Živný, FOCS 2012, 53rd Annual Symposium on Foundations of Computer Science, IEEE, 2012, pp. 669--678] to study the existence of such relaxations, we are able to provide a much broader class of half-integral polytopes with the required properties. Our results unify and significantly extend the previously known cases, and yield a range of new and improved FPT algorithms, including an $O^(\|\Sigma\|^{2k})$-time algorithm for node-deletion Unique Label Cover and an $O^(4^k)$-time algorithm for Group Feedback Vertex Set where the group is given by oracle access. The latter result also implies the first single-exponential time FPT algorithm for Subset Feedback Vertex Set, answering an open question of Cygan et al. [Algorithmica, 74 (2016), pp. 630--642]. Additionally, we propose a network-flow-based approach to solve several cases of the relaxation problem. This gives the first linear-time FPT algorithm to edge-deletion Unique Label Cover.
Sponsorship	Ministry of Education, Culture, Sports, Science, and Technology. Japan Society for the Promotion of Science
Starting Page	1377
Ending Page	1411
Page Count	35
File Format	PDF
ISSN	00975397
DOI	10.1137/140962838
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	4 (Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012))
Volume Number	45
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2016-08-09
Access Restriction	Subscribed
Subject Keyword	$k$-submodularity Graph algorithms fixed parameter tractability
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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

Half-integrality, LP-branching and FPT Algorithms (2014)

Half-integrality, LP-branching and FPT Algorithms

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

A $c^k n$ 5-Approximation Algorithm for Treewidth

Interval Completion Is Fixed Parameter Tractable

FPT algorithms for packing k-safe spanning rooted sub(di)graphs

Designing FPT Algorithms for Cut Problems Using Randomized Contractions

Constant-Factor FPT Approximation for Capacitated k-Median

Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

Half-integrality, LP-branching, and FPT Algorithms

Similar Documents

Half-integrality, LP-branching and FPT Algorithms (2014)

Half-integrality, LP-branching and FPT Algorithms

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

A $c^k n$ 5-Approximation Algorithm for Treewidth

Interval Completion Is Fixed Parameter Tractable

FPT algorithms for packing k-safe spanning rooted sub(di)graphs

Designing FPT Algorithms for Cut Problems Using Randomized Contractions

Constant-Factor FPT Approximation for Capacitated k-Median

Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

Half-integrality, LP-branching, and FPT Algorithms