Goyal, Prachi ;
Misra, Pranabendu ;
Panolan, Fahad ;
Philip, Geevarghese ;
Saurabh, Saket
Finding Even Subgraphs Even Faster
Abstract
Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k edges(arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the
vertices have even degreeswhere the resulting graph is Eulerian,the problem is called Undirected Eulerian Edge Deletion. The corresponding
problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same indegree as its
outdegree is called Directed Eulerian Edge Deletion. Cygan et al.[Algorithmica, 2014] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time
2^O(k log k)n^O(1). They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time
2^O(k)n^O(1). It was also posed as an open problem at the School on Parameterized Algorithms and Complexity 2014, Bedlewo, Poland.
In this paper we answer their question in the affirmative: using the technique of computing representative families of cographic matroids we design algorithms which solve these problems in time 2^O(k)n^O(1). The crucial insight we bring to these problems is to view the solution as an independent set of a cographic matroid. We believe that this viewpoint/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.
BibTeX  Entry
@InProceedings{goyal_et_al:LIPIcs:2015:5633,
author = {Prachi Goyal and Pranabendu Misra and Fahad Panolan and Geevarghese Philip and Saket Saurabh},
title = {{Finding Even Subgraphs Even Faster}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {434447},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897972},
ISSN = {18688969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5633},
URN = {urn:nbn:de:0030drops56336},
doi = {10.4230/LIPIcs.FSTTCS.2015.434},
annote = {Keywords: Eulerian Edge Deletion, FPT, Representative Family.}
}
14.12.2015
Keywords: 

Eulerian Edge Deletion, FPT, Representative Family. 
Seminar: 

35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Issue date: 

2015 
Date of publication: 

14.12.2015 