BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

R. Krithika

R. Krithika contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsComputational Complexitymath.CO

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2026arXiv

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction

In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obtain a biclique and a balanced biclique, respectively. We first prove that these problems are NP-complete even when the input graph is bipartite. Next, we study the parameterized complexity of these problems and show that they admit single exponential-time FPT algorithms when parameterized by the number k of edge contractions. Then, we show that Balanced Biclique Contraction admits a quadratic vertex kernel while Biclique Contraction does not admit any polynomial compression (or kernel) under standard complexity-theoretic assumptions. We also give faster FPT algorithms for contraction to restricted bicliques.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterized and Exact Algorithms for Class Domination Coloring

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighbourhood of some vertex. The minimum number of colors required for any cd-coloring of $G$, denoted by $χ_{cd}(G)$, is called the class domination chromatic number (cd-chromatic number) of $G$. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph $G$ on $n$ vertices, find its cd-chromatic number. (2) Given a graph $G$ and integers $k$ and $q$, can we delete at most $k$ vertices such that the cd-chromatic number of the resulting graph is at most $q$? For the first problem, we give an exact algorithm with running time $\Oh(2^n n^4 \log n)$. Also, we show that the problem is \FPT\ with respect to the number $q$ of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with $\Oh(q^3)$ vertices. For the second (deletion) problem, we show \NP-hardness for each $q \geq 2$. Further, on split graphs, we show that the problem is \NP-hard if $q$ is a part of the input and \FPT\ with respect to $k$ and $q$ as combined parameters. As recognizing graphs with cd-chromatic number at most $q$ is \NP-hard in general for $q \geq 4$, the deletion problem is unlikely to be \FPT\ when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for $q \in \{2,3\}$ using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Dirac-type Characterization of k-chordal Graphs

Characterization of k-chordal graphs based on the existence of a "simplicial path" was shown in [Chv{á}tal et al. Note: Dirac-type characterizations of graphs without long chordless cycles. Discrete Mathematics, 256, 445-448, 2002]. We give a characterization of k-chordal graphs which is a generalization of the known characterization of chordal graphs due to [G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25, 71-76, 1961] that use notions of a "simplicial vertex" and a "simplicial ordering".

0 citations0 reviewsNo code linkedOpen access