NDLI: Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Gupta, Sushmita Raman, Venkatesh Saurabh, Saket
Copyright Year	2012
Abstract	We show that for a fixed $r$, the number of maximal $r$-regular induced subgraphs in any graph with $n$ vertices is upper bounded by $\mathcal{O}(c^n)$, where $c$ is a positive constant strictly less than $2$. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of $3^{n/3}$ on the number of maximal independent sets of a graph on $n$ vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal $r$-regular induced subgraphs possible in a graph on $n$ vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal $r$-regular induced subgraphs in time $\mathcal{O}(c^n n^{\mathcal{O}(1)})$. A related question is that of finding a maximum-sized $r$-regular induced subgraph. Given a graph $G=(V,E)$ on $n$ vertices, the Maximum $r$-Regular Induced Subgraph (M-$r$-RIS) problem asks for a maximum-sized subset of vertices, $R \subseteq V$, such that the induced subgraph on $R$ is $r$-regular. As a by-product of the enumeration algorithm, we get a $\mathcal{O}(c^n)$ time algorithm for this problem for any fixed constant $r$, where $c$ is a positive constant strictly less than $2$. Furthermore, we use the techniques and results obtained in the paper to obtain improved exact algorithms for a special case of the Induced Subgraph Isomorphism problem, namely, the Induced $r$-Regular Subgraph Isomorphism problem, where $r$ is a constant, the $\delta$-Separating Maximum Matching problem and the Efficient Edge Dominating Set problem.
Starting Page	1758
Ending Page	1780
Page Count	23
File Format	PDF
ISSN	08954801
DOI	10.1137/09077850X
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	4
Volume Number	26
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2012-12-12
Access Restriction	Subscribed
Subject Keyword	Enumeration in graph theory maximal $r$-regular subgraphs exact exponential time algorithms Graph algorithms combinatorial upper and lower bounds
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

Fast exponential algorithms for maximum -regular induced subgraph problems (2006)

Finding induced subgraphs via minimal triangulations.

Finding induced subgraphs via minimal triangulations (2010).

Large nearly regular induced subgraphs

Parameterized complexity of finding regular induced subgraphs (2006)

Finding induced subgraphs via minimal triangulations (2009)

Large nearly regular induced subgraphs

Parameterized complexity of finding regular induced subgraphs (2006)

Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs

Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds

Similar Documents

Fast exponential algorithms for maximum -regular induced subgraph problems (2006)

Finding induced subgraphs via minimal triangulations.

Finding induced subgraphs via minimal triangulations (2010).

Large nearly regular induced subgraphs

Parameterized complexity of finding regular induced subgraphs (2006)

Finding induced subgraphs via minimal triangulations (2009)

Large nearly regular induced subgraphs

Parameterized complexity of finding regular induced subgraphs (2006)

Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs

Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds